Problem:


Score : 300 points

Problem Statement

You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges.

The i-th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i.  

An edge whose removal disconnects the graph is called a bridge.

Find the number of the edges that are bridges among the M edges.  

Notes

A self-loop is an edge i such that a_i=b_i (1 \leq i \leq M).

Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j (1 \leq i<j \leq M).

An undirected graph is said to be connected when there exists a path between every pair of vertices.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq min(N(N−1)⁄2,50)

1 \leq a_i<b_i \leq N

The given graph does not contain self-loops and double edges.

The given graph is connected.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

Output

Print the number of the edges that are bridges among the M edges.

Sample Input 1

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

Sample Output 1

4

The figure below shows the given graph:

The edges shown in red are bridges. There are four of them.

Sample Input 2

3 3
1 2
1 3
2 3

Sample Output 2

0

It is possible that there is no bridge.

Sample Input 3

6 5
1 2
2 3
3 4
4 5
5 6

Sample Output 3

5

It is possible that every edge is a bridge.



Sample input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7


Sample output:
4

Submission status: Accepted

Solution code:

from collections import deque

def read_input():
    n, m = map(int, input().split())

    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a, b))

    return n, m, edges


def check_graph(n, edges):
    nodes = list(range(1, n + 1))
    nodes.sort()

    trans = {i: [] for i in nodes}
    for e in edges:
        trans[e[0]].append(e[1])
        trans[e[1]].append(e[0])

    node_q = deque()
    node_q.appendleft(nodes[0])
    searched = []
    while len(node_q) > 0:
        curr = node_q.popleft()
        searched.append(curr)
        target = trans[curr]

        for t in target:
            if t not in searched:
                node_q.appendleft(t)

        searched = list(set(searched))
        searched.sort()

    if searched == nodes:
        return True
    else:
        return False


def submit():
    n, m, edges = read_input()

    count = 0
    for t in range(m):
        test = [e for i, e in enumerate(edges) if i != t]
        if check_graph(n, test):
            count += 1

    print(m - count)

if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import random
import pprint
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v):
    # ノードに訪れた
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  # そもそもvとv2が辺でつながっていない
            continue
        if visited[v2] == True:  # もう見た
            continue
        dfs(v2)


# nは頂点の数
n, m = MI()
ans = 0
sides = [LI() for _ in range(m)]
# 隣接行列を用いてグラフの管理をする
# graph = [[False] * n for _ in range(n)]

# もしグラフ全体が連結ならばuf[i]=iとなる頂点がただ1つだけある
# Union-Find
for i in range(m):

    # 最初各ノードの根は自分自身
    node = [k for k in range(n)]
    
    for j, side in enumerate(sides):
        
        # 連結しない
        if i == j:
            continue

        unite(side[0]-1, side[1]-1)

    # 根が自分自身であるものが2つ以上存在する場合、グラフは非連結である
    # 1である場合連結なのでのぞいた辺は橋「ではない」
    if sum(node[num] == num for num in range(len(node))) != 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import random
import pprint
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v):
    # ノードに訪れた
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  # そもそもvとv2が辺でつながっていない
            continue
        if visited[v2] == True:  # もう見た
            continue
        dfs(v2)


# nは頂点の数
n, m = MI()
ans = 0
sides = [LI() for _ in range(m)]
visited = [False] * n
# 隣接行列を用いてグラフの管理をする
graph = [[False] * n for _ in range(n)]

# 初期化、graph[i-1][j-1] = 1ならば頂点i,jは連結している
for a, b in sides:
    graph[a-1][b-1] = True
    graph[b-1][a-1] = True 

# pprint.pprint(graph)

for a, b in sides:
    # 辺の削除
    graph[a-1][b-1] = False
    graph[b-1][a-1] = False

    for i in range(n):
        visited[i] = False
    
    dfs(0)

    # 探索実行後訪れていないノードが1つでもあれば
    # 削除した辺は橋である
    for i in range(n):
        if visited[i] == False:
            ans += 1
            break

    # 辺を元に戻す
    graph[a-1][b-1] = True
    graph[b-1][a-1] = True

print(ans)

Submission status: Accepted

Solution code:
def main():
	N, M = map(int,input().split())
	V = [[] for _ in range(N+1)]
	a = [0]*M
	b = [0]*M
	for i in range(M):
		a[i], b[i] = map(int,input().split())
		V[a[i]].append(b[i])
		V[b[i]].append(a[i])
	ans = 0

	for i in range(M):
		visited = [False]*(N+1)
		stack = [1]
		while stack:
			v = stack.pop()
			if visited[v]:
				continue
			visited[v] = True
			for n in V[v]:
				if (n == a[i] and v == b[i]) or (n == b[i] and v == a[i]):
					continue
				stack.append(n)
		if not(all(visited[1:])):
			ans += 1
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
ab = [list(map(lambda x:int(x)-1,input().split(" "))) for x in range(M)]

p = [[False]*N for x in range(N)]

for a in ab:
    p[a[0]][a[1]] = True
    p[a[1]][a[0]] = True

def dfs(v):
    c[v] = True
    for i in range(N):
        if p[v][i] and not(c[i]):
            dfs(i)

s = 0
for a in ab:
    p[a[0]][a[1]] = False
    p[a[1]][a[0]] = False
    c = [False]*N
    dfs(a[0])
    if False in c:
        s += 1
    p[a[0]][a[1]] = True
    p[a[1]][a[0]] = True

print(s)

Submission status: Accepted

Solution code:
def Con(V,E):
  C1,C2=set(),set()
  C1.add(1)
  while len(C1)>len(C2):
    for v in V:
      if v in C1 and v not in C2:
        for e in E:
          if e[0]==v:
            C1.add(e[1])
          elif e[1]==v:
            C1.add(e[0])
        C2.add(v)
  if len(C1)==len(V):
    return True
  else:
    return False
n,m=map(int,input().split())
V=[int(i) for i in range(1,n+1)]
E=[]
for i in range(m):
  s,g=map(int,input().split())
  E.append([s,g])
ans=0
for i in range(m):
  if Con(V,E[:i]+E[i+1:])==False:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def Con(V,E):
  C1,C2=set(),set()
  C1.add(1)
  C2.add(1)
  for e in E:
    if e[0]==1:
      C1.add(e[1])
    elif e[1]==1:
      C1.add(e[0])
  while len(C1)>len(C2):
    for c1 in V:
      if c1 in C1 and c1 not in C2:
        for e in E:
          if e[0]==c1:
            C1.add(e[1])
          elif e[1]==c1:
            C1.add(e[0])
        C2.add(c1)
  if len(C1)==len(V):
    return True
  else:
    return False
n,m=map(int,input().split())
V=[int(i) for i in range(1,n+1)]
E=[]
for i in range(m):
  s,g=map(int,input().split())
  E.append([s,g])
ans=0
for i in range(m):
  if Con(V,E[:i]+E[i+1:])==False:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from copy import*
class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True

    
n,m=map(int,input().split())
ans=0

Input=[list(map(int,input().split()))for s in m*[0]]
for i in Input:
    uni=UNION_FIND(n)
    s=deepcopy(Input)
    s.remove(i)
    for j in s:
        x,y=j
        x-=1
        y-=1
        uni.union(x,y)
#    print(uni.parent)
    g,h=i
    g-=1
    h-=1
    if uni.root(g)!=uni.root(h):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(M)]

class Unionfind:
    def __init__(self, num):
        self.par = [i for i in range(num+1)]
        self.rank = [0] * (num+1)

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if self.rank[ru] < self.rank[rv]:
            self.par[ru] = rv
        else:
            self.par[rv] = ru
            if self.rank[ru] == self.rank[rv]:
                self.rank[ru] += 1

    def same(self, u, v):
        return self.root(u) == self.root(v)

ans = 0

for i in range(M):
    uni = Unionfind(N)
    for j in range(M):
        if i != j:
            uni.unite(data[j][0], data[j][1])
        else:
            check = j
    if not uni.same(data[check][0], data[check][1]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())

connect = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    connect[a-1][b-1] = 1
    connect[b-1][a-1] = 1

notbridge = 0


for i in range(n):
    for j in range(n):
        if connect[i][j] == 1:
            connect[i][j] = 0
            connect[j][i] = 0
            stack =[1]
            visited = [1]
            while stack:
                p = stack.pop()
                for k in range(n):
                    if connect[p][k] == 1:
                        if k not in visited:
                            stack.append(k)
                            visited.append(k)
            if len(visited) == n:
                notbridge += 1
            connect[i][j] = 1
            connect[j][i] = 1



print(m-notbridge//2)

Submission status: Accepted

Solution code:
import numpy as np

n,m = map(int, input().split())

connect = np.zeros((n,n))

for i in range(m):
    a, b = map(int, input().split())
    connect[a-1, b-1] = 1
    connect[b-1, a-1] = 1

notbridge = 0


for i in range(n):
    for j in range(n):
        if connect[i,j] == 1:
            connect[i,j] = 0
            connect[j,i] = 0
            stack =[1]
            visited = [1]
            while stack:
                p = stack.pop()
                for k in range(n):
                    if connect[p,k] == 1:
                        if k not in visited:
                            stack.append(k)
                            visited.append(k)
            if len(visited) == n:
                notbridge += 1
            connect[i,j] = 1
            connect[j,i] = 1



print(m-notbridge//2)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        """ノード数nの配列を作る

        親の番号を格納する
        -> 自分が根だった場合は、-(その集合のサイズ)とする
        作るときはparentの値を全て-1にする
        こうすると全てバラバラになる
        """
        self.parent = [-1 for _ in range(n)]

    def root(self, x):
        """要素xの根の番号を返す
        """
        if self.parent[x] < 0:
            # 自分が根
            return x
        # 要素xの親を要素xの根に変えておく
        # 次の呼び出しが早くなる
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def size(self, x):
        """要素xの所属するグループの頂点数を調べる

        根のparentにサイズが格納されている
        """
        return -self.parent[self.root(x)]

    def merge(self, x, y):
        """xとyを結合する
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False

        #大きい方(x)に小さい方(y)をくっつけたい
        if self.size(x) < self.size(y):
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True

N,M=map(int, input().split())

AB= [list(map(int, input().split())) for _ in range(M)]
ans=0
for i in range(M):
    uf = UnionFind(N)
    hens = AB[0:i]+AB[i+1:]
    for hen in hens:
        x,y = hen
        uf.merge(x-1, y-1)

    if uf.size(0) != N:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

point = [[] for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    if b not in point[a-1]:
        point[a-1].append(b)
    if a not in point[b-1]:
        point[b-1].append(a)

ans = 0
while True:
    idx, flg = 0, 0
    for i in point:
        if len(i) == 1:
            flg = 1
            point[i[0]-1].remove(idx+1)
            point[idx] = []
            ans += 1
        idx += 1
    if flg == 0:
        break

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
hen = []
for i in range(M):
    a, b = map(int, input().split())
    hen.append([a, b])
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

ans = 0
import copy

def dfs(node, visited, gr):
    visited.append(node)
    for cand in gr[node]:
        if cand not in visited:
            dfs(cand, visited, gr)
    return visited

def gcopy(arr):
    new = []
    for a in arr:
        new.append(copy.copy(a))
    return new

for i in range(M):
    a, b = hen[i]
    g = gcopy(graph)
    g[a-1].remove(b-1)
    g[b-1].remove(a-1)
    visited = []
    ans += 1 if len(dfs(0, visited, g)) == N else 0

print(M-ans)

Submission status: Accepted

Solution code:
import copy

N,M=map(int,input().split())
R=[]
for i in range(M):
    a,b=map(int,input().split())
    R.append((a,b))

def connected(N,roads):
    arrived=[0]*(N+1)
    q=[]
    q.append(1)
    try:
        while True:
            loc=q.pop()
            arrived[loc]=1
            for r in roads:
                if r[0]==loc and arrived[r[1]]==0:
                    q.append(r[1])
                if r[1]==loc and arrived[r[0]]==0:
                    q.append(r[0])
    except IndexError:
        pass
    return sum(arrived)==N

ans=0
for i in range(M):
    roads = copy.deepcopy(R)
    del roads[i]
    if not connected(N,roads):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

answer = 0
for i in range(M):
  temp = AB[:i] + AB[i+1:]
  ai, bi = AB[i]
  uf = UnionFind()
  for ab in temp:
    a,b = ab
    uf.unite(a,b)
  answer += not uf.is_union(ai, bi)


print(answer)

Submission status: Accepted

Solution code:
N, M = map( int, input().split() )
AdjMatric = [ [False]*N for _ in range(N) ]
for _ in range(M):
    a, b = map( int, input().split() )
    a -= 1
    b -= 1
    AdjMatric[a][b] = True
    AdjMatric[b][a] = True


ans = 0
for i in range(N):
    for j in range(i+1,N):
        if AdjMatric[i][j] == False: continue
        # 橋 i <-> j を取り除いたときに i -> j へ行けるかを全探索
        AdjMatric[i][j] = False
        isVisited = [False]*N
        s = [i]
        while s:
            tmp = s.pop()
            if isVisited[tmp]: continue
            isVisited[tmp] = True
            for k in range(N):
                if AdjMatric[tmp][k] == True: s.append(k)
        if isVisited[j] == False: ans += 1
        AdjMatric[i][j] = True

print( ans )

Submission status: Accepted

Solution code:

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]

ad = [[0]*n for i in range(n)]

for x in ab:
    ad[x[0]-1][x[1]-1] = 1
    ad[x[1]-1][x[0]-1] = 1

nodes = [0]*n
ans = 0
flag = True
while flag:
    flag = False
    for i in range(n):
        if nodes[i] == 0 and sum(ad[i]) == 1:
            ans +=1
            nodes[i] = 1
            flag = True
            for j in range(n):
                if ad[i][j] == 1:
                    ad[j][i] =0
print(ans)

Submission status: Accepted

Solution code:
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

# Union-Find #
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N,M = IL()
ab = [IL() for i in range(M)]

cnt = 0
for k in range(M):
    par=[0 for i in range(N)]
    rnk=[0 for i in range(N)]
    init(N)
    for i in range(M):
        if k == i:
            continue
        else:
            a,b = ab[i]
            unite(a-1,b-1)
    tmp = find(0)
    for i in range(1,N):
        if tmp == find(i):
            continue
        else:
            cnt += 1
            break
print(cnt)

Submission status: Accepted

Solution code:

import itertools
import collections
import bisect

# Union find
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]  # 負の値の場合根を表す。絶対値はツリーの高さ 正の値は次の要素を返す、根まで続く
        self.size = [1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
        return

    def group_size(self, x):
        return self.size[self.find(x)]


def main():
    N, M = map(int, input().split())
    st = []
    en = []
    for _ in range(M):
        i, j = map(int, input().split())
        st.append(i-1)
        en.append(j-1)

    # print(st)
    # print(en)
    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(len(st)):
            if i == j:
                continue
            uf.union(st[j], en[j])
        group = uf.find(0)
        if not all([uf.find(i) == group for i in range(N)]):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える

N,M = map(int,input().split())

edge = []
pass_edge = []
for i in range(M):
    a,b = map(int,input().split())
    if a < b:
        a,b = b,a#つねaの方が大きい
    if a==b:
        pass_edge.append([a,b])
    else:
        edge.append([a,b])

sorted_edge = sorted(edge)

bridge = {}
for i in range(1,N+1):
    bridge[i] = []

latest_bridge = [0,0]
for edge_i in sorted_edge:
    #edge = [a,b]
    if latest_bridge == edge_i:
        pass_edge.append(edge)
        pass
    else:
        latest_bridge = edge_i
        for port in range(2):
            bridge[edge_i[port]] = bridge[edge_i[port]]+[edge_i[port-1]]

# print(bridge)

def check(ie):
    a,b = ie
    used.append(a)
    copy_bridge = copy.deepcopy(bridge)
    copy_bridge[a] = list(set(copy_bridge[a])-set([b]))
    move = copy_bridge[a]
    isolate = 1
    while len(move)>0:
        pos = move.pop()
        if pos in used:
            pass
        elif pos == b:
            isolate = 0
        else:
            move = move+list(set(copy_bridge[pos]+used)-set(used))
            used.append(pos)
    return isolate

ans = 0

for ie in edge:
    # print("bi",ie)
    if ie in pass_edge:
        pass
    else:
        used = []

        ans += check(ie)
        # print(ans)

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split());a,ans=[[],[]],0
for i in range(m):aa,bb=map(int,input().split());a[0].append(aa);a[1].append(bb)
flag=True
while flag:
  flag=False
  for i in range(1,n+1):
    c=0
    p=[]
    for j in range(len(a[0])):
      if a[0][j]==i:c+=1;p.append(j)
      if a[1][j]==i:c+=1;p.append(j)
      if c>1:break
    if c==1:
      ans+=1
      del a[0][p[0]],a[1][p[0]]
      flag=True
      break
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(item) for item in input().split()]
edge = [[0]*n for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

ans = 0
order = 0
pre = [-1]*n
low = [-1]*n
def dfs(node, prev):
    global order, ans
    pre[node] = order
    low[node] = order
    order += 1
    for to in range(n):
        if to == prev or edge[node][to] == 0:
            continue
        if pre[to] == -1:
            ret = dfs(to, node)
            low[node] = min(low[node], ret)
        else:
            low[node] = min(low[node], pre[to])
        if pre[node] < low[to]:
            ans += 1
    return low[node]
    
dfs(0, -1)
print(ans)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
#隣接行列の作成
rinsetsu=[[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b=[int(j) for j in input().split()]
    rinsetsu[a-1][b-1]=1
    rinsetsu[b-1][a-1]=1
visited=[False]*n
ans=0
flag=True
#隣接している島が1つ→訪問済みにしその隣接を隣接行列から削除
#繰り返していくと連結(ループ)だけが残る
while flag:
    flag=False
    for i in range(n):
        if not visited[i] and sum(rinsetsu[i])==1:
            visited[i]=True
            ans+=1
            flag=True
            for j in range(n):
                if rinsetsu[i][j]==1:
                    rinsetsu[j][i]=0
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import queue
n,m = map(int,input().split())

V = np.zeros((n+1,n+1),dtype=bool)
E = []
for i in range(m):
    a,b = map(int,input().split())
    V[a][b] = True
    V[b][a] = True
    E.append((a,b))
def BFS(x,y):
    mark = [False]*(n+1)
    q = queue.Queue()
    q.put(x)
    while not q.empty():
        p = q.get()
        if p == y:
            return True
        mark[p] = True
        for i in range(1,n+1):
            if V[p][i] and not mark[i]:
                q.put(i)
    return False
res = 0

for a,b in E:
    V[a][b] = False
    V[b][a] = False
    if not BFS(a,b):
        res+=1

    V[a][b] = True
    V[b][a] = True
print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
brighes=[list(map(lambda x:int(x)-1,input().split()))for i in range(m)]
neighbor=[set()for i in range(n)]
for brighe in brighes:
  v1,v2=brighe
  neighbor[v1].add(v2)
  neighbor[v2].add(v1)
  
ans=0
for brighe in brighes:
  v=[0 for i in range(n)]
  v[brighe[0]]=1
  stack=[]
  for a in neighbor[brighe[0]]:
    if a!=brighe[1]:
      stack.append(a)
  while stack!=[]:
    a=stack.pop()
    v[a]=1
    for b in neighbor[a]:
      if v[b]!=1:
        stack.append(b)
  if v[brighe[1]]==0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [list() for i in range(N)]
A = []
B = []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    D[a-1].append(b-1)
    D[b-1].append(a-1)
d = [0]*N
d[0] = 1
cnt = 0


def dfs(x):
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)


for i in range(M):
    D[A[i] - 1].remove(B[i] - 1)
    D[B[i] - 1].remove(A[i] - 1)

    d = [0]*N
    d[0] = 1
    dfs(0)

    if all(d) is False:
        cnt += 1
    D[A[i] - 1].append(B[i] - 1)
    D[B[i] - 1].append(A[i] - 1)

print(cnt)

Submission status: Accepted

Solution code:
def root(x):
    if uf[x] == x:
        return x
    uf[x] = root(uf[x])
    return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,input().split())
edge = []
for i in range(M):
    edge.append(list(map(int,input().split())))

cnt = 0
for i in range(M):
    uf = [i for i in range(N+1)]
    for j in range(M):
        if i != j:
            unite(edge[j][0], edge[j][1])
    for j in range(N):
        if not same(1, j+1):
            cnt += 1
            break
print(str(cnt))

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, num):
        self.parent = [-1 for i in range(num + 1)]

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.size(x) > self.size(y):
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y

    def size(self, x):
        return -self.parent[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
lis = []
count = 0
for i in range(m):
    lis.append(list(map(int, input().split())))
for i in range(m):
    u = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        u.unite(lis[j][0], lis[j][1])
    if not u.same(lis[i][0], lis[i][1]):
        count += 1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])


    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
def C(x):
    U=UnionFind(n)
    for i in range(m):
        if i==x :
            continue
        U.unite(ab[i][0]-1, ab[i][1]-1)
    for i in range(n):
        for j in range(n):
            if not U.same(i, j):
                return False
    return True
ans=0
for y in range(m):
    if not C(y):
        ans+=1
print(ans)