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

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

A,B=[0]*M,[0]*M
graph=[[] for _ in range(N)]
for i in range(M):
    A[i],B[i]=map(int,input().split())
    A[i]-=1
    B[i]-=1
    graph[A[i]].append(B[i])
    graph[B[i]].append(A[i])

def bfs(graph,visited,start):
    queue=deque([start])
    visited[start]=True
    while queue:
        vartex=queue.popleft()
        for new_vartex in graph[vartex]:
            if visited[new_vartex]==False:
                visited[new_vartex]=True
                queue.append(new_vartex)
    
    if False in visited:
        return False
    else:
        return True

ans=0
for i in range(M):
    if i == 0:
        graph[A[0]].remove(B[0])
        graph[B[0]].remove(A[0])
    else:
        graph[A[i]].remove(B[i])
        graph[B[i]].remove(A[i])
        graph[A[i-1]].append(B[i-1])
        graph[B[i-1]].append(A[i-1])
    
    visited=[False]*N
    if bfs(graph,visited,0):
        continue
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy as cp

def isTree(graph,know=[],now=0):
    if not know: know = [0]*len(graph[0])
    know[now] = 1
    for next in range(n):
        if know[next]==1 or graph[now][next]==0: continue
        else: isTree(graph,know,next)
    if all(know): return 1
    else: return 0

n,m = map(int,input().split())
ab = np.array([list(map(int,input().split()))for i in range(m)])
a,b = ab.T[0]-1, ab.T[1]-1

G = [[0]*n for i in range(n)]
for i in range(m):
    aa,bb = a[i],b[i]
    G[aa][bb],G[bb][aa] = 1,1

# 除外する辺を決めてループ
ans = 0
for i in range(m):
    aa,bb = a[i],b[i]
    tree = cp.deepcopy(G)
    tree[aa][bb],tree[bb][aa] = 0,0
    if not isTree(tree): ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy as cp

def isTree(now=0):
    know[now] = 1
    for next in range(n):
        if know[next]==1 or graph[now][next]==0: continue
        else: isTree(next)
    if all(know): return 1
    else: return 0

# nは頂点の数
n, m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0]-1,ab.T[1]-1

#隣接行列
G = [[0] * n for _ in range(n)]
for aa,bb in zip(a,b): G[aa][bb],G[bb][aa] = 1,1

ans = 0
for x,y in zip(a,b):
    graph = cp.deepcopy(G)
    graph[x][y],graph[y][x] = 0,0
    know = [0]*(n)
    if not isTree(): ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(G, v, visited):
    """G: graph, v: vertex"""
    visited[v] = True
    for c in G[v]:
        if visited[c]:
            continue
        dfs(G, c, visited)


def main():
    N, M = map(int, input().split())
    a = [None] * M
    b = [None] * M
    G = [[] for _ in range(N)]
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        a[i] -= 1
        b[i] -= 1
        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    ans = 0
    for i in range(M):
        # remove an adge
        G[a[i]].remove(b[i])
        G[b[i]].remove(a[i])

        visited = [False] * N
        visited[0] = True
        dfs(G, 0, visited)

        if visited.count(True) != N:
            ans += 1

        # restore an edge
        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def dfs(G, v, visited):
    visited[v] = True
    stack = deque([v])
    while stack:
        v = stack.pop()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = True
            stack.append(u)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    a = [0] * M
    b = [0] * M
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        a[i] -= 1
        b[i] -= 1
        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    ans = 0
    for i in range(M):
        G[a[i]].remove(b[i])
        G[b[i]].remove(a[i])

        visited = [False] * N
        dfs(G, 0, visited)

        if not all(visited):
            ans += 1

        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, visited):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = True
            queue.append(u)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    a = [0] * M
    b = [0] * M
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        a[i] -= 1
        b[i] -= 1
        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    ans = 0
    for i in range(M):
        G[a[i]].remove(b[i])
        G[b[i]].remove(a[i])

        visited = [False] * N
        bfs(G, 0, visited)

        if not all(visited):
            ans += 1

        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(G, v, visited):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = True
            queue.append(u)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    a = [0] * M
    b = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
        a[i] = u
        b[i] = v

    ans = 0
    for i in range(M):
        G[a[i]].remove(b[i])
        G[b[i]].remove(a[i])

        visited = [False] * N
        bfs(G, 0, visited)

        if not all(visited):
            ans += 1

        G[a[i]].append(b[i])
        G[b[i]].append(a[i])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
d = []
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    d.append((a,b))
#print(d)
pa = None

def root(a):
    if pa[a] == a:
        return a
    else:
        pa[a] = root(pa[a])
        return pa[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    aa = root(a)
    bb = root(b)
    if aa == bb:
        return
    pa[aa] = bb

ans = 0
for i in range(m):
    pa = [x for x in range(n)]
    for j,v in enumerate(d):
        #(i,j,v)
        if i == j:continue
        a,b = v
        unite(a,b)
    a,b = d[i]
    if not is_same(a,b):
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def Union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
n,m = map(int,input().split())
bridge = []
for i in range(m):
    s,t = map(lambda x:int(x) - 1,input().split())
    bridge.append([s,t])
cnt = 0
# 取り除く辺を考える
for i in range(m):
    Uni = UnionFind(n)
    for j,root in enumerate(bridge,start = 0):
        if i == j: # 一緒のところをのぞいている
            continue
        s,t = root
        Uni.Union(s,t)
    # ここで、そのiのところ(除いてるところ)を調べる
    s,t = bridge[i]
    # 親が一緒なら、別にそこは橋じゃない それが無くても行けるから
    if not Uni.same(s,t):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
G=[[] for _ in range(N)]
H=[]
import sys
sys.setrecursionlimit(10**6)
for i in range(M):
    a,b=map(int, input().split())
    G[a-1].append((b-1,i))
    G[b-1].append((a-1,i))
    H.append((i,a-1,b-1))
def dfs(start, goal, banned):
    done[start]=1
    if start==goal:
        ok[0]=True
    for t in G[start]:
        nex, num=t
        if num==banned:
            continue
        elif done[nex]==-1:
            dfs(nex, goal, banned)
    
ans=M
for h in H:
    i,a,b=h
    done=[-1]*N
    ok=[False]
    dfs(a,b,i)
    if ok[0]:
        ans-=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
edge_ls = [0] * m
for i in range(m):
    a,b = map(int,input().split())
    edge_ls[i] = [a,b]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        '''
        xとyは-=1して使うのが基本
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
edge_q = deque(edge_ls)
num_bridge = 0
for i in range(m):
    tar = edge_q.popleft()
    uf = UnionFind(n)
    for a,b in edge_q:
        a -= 1
        b -= 1
        uf.union(a,b)
    if not uf.group_count() == 1:
        num_bridge += 1
    edge_q.append(tar)
print(num_bridge)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

n,m = LI()
ab = [LI() for _ in range(m)]
ans = 0
for i in range(m):
    par = [i for i in range(n)]
    rank = [0] * n
    for j in range(m):
        if i == j:
            continue
        a, b = ab[j]
        if root(a-1) != root(b-1):
            union(a-1, b-1)
    cnt = len(set([root(i) for i in range(n)]))
    if cnt > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
sys.setrecursionlimit(10**9)
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
#グラフの閉路検出だけ
def resolve():
    N,M=pin()
    gragh={(v+1):[] for v in range(N)}
    for i in range(M):
        a,b=pin()
        gragh[a].append(b)
        gragh[b].append(a)
    #print(gragh)#->ok
    heiro=dict()
    heiro2=set()
    def dfs(v_from,travel,prev=None):
        tra=list(travel)    
        for v_to in gragh[v_from]:
            #stoper
            if v_to==prev:
                #print("a")
                continue
            if v_to in(tra):#closed 
                dicset=set()
                f=0
                kyori=0
                for n,t in enumerate(tra):
                    if v_to==t:
                        f=1
                    if f==1:
                        kyori+=1
                        dicset.add(t)
                if len(dicset)>2:
                    dicset=frozenset(dicset)
                    heiro.setdefault(dicset,kyori)
                    #print(gragh[v_from],(prev,v_from,v_to),dicset,tra)
                    break
                continue
            #caller
            prev=v_from
            tra2=tra[:]
            tra2.append(v_to)  
            #print(tra,v_to) 
            dfs(v_to,tra2,prev)

        return
        
    dfs(1,[1])
    #print(heiro)
    for j in (heiro.keys()):
        temp=set(j)
        #print(temp)
        for k in temp:
            heiro2.add(k)
    #print(heiro2)
    seen=heiro2.copy()
    global ans
    def dfs2(f):
        global ans
        if  f in seen:return
        ans+=1
        seen.add(f)
        for t in gragh[f]:
            dfs2(t)
            
    ans=0        
    for i in range(1,N+1):
        if i in seen:continue
        dfs2(i)
    if len(heiro2)==0:ans-=1
    print(ans)    
#%%submit!
resolve()

Submission status: Accepted

Solution code:
from collections import deque
n,m = tuple(map(int,input().split()))

edge = []

for i in range(m):
  edge.append(tuple(map(lambda a:int(a)-1,input().split())))
  
matrix = [[0]*n for _ in range(n)]
  
for a,b in edge:
  matrix[a][b] = 1
  matrix[b][a] = 1
  
ans = 0

for a,b in edge:
  matrix[a][b] = 0
  matrix[b][a] = 0
  
  checked = [False]*n
  queue = deque([0])
  while(len(queue)>0):
    q = queue.popleft()
    if checked[q]:
      continue
    else:
      checked[q] = True
      mat = matrix[q]
      for i in range(n):
        if mat[i] == 1:
          queue.append(i)
  if not all(checked):
    ans+=1
  
  matrix[a][b] = 1
  matrix[b][a] = 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

edges = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(M)]

def isBride(i):
    tree = UnionFind(N)
    for j, (a, b) in enumerate(edges):
        if i == j:
            continue
        tree.union(a, b)
    return tree.getComponent() > 1

print(len([0 for i in range(M) if isBride(i)]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
eab=[]
for i in range(m):
    a,b=map(int,input().split())
    e[a].append(b)
    e[b].append(a)
    eab.append([a,b])

def dfs(used,count,v):

    used[v]=True
    c=count+1
    ev=e[v]
    for ei in ev:
        if(used[ei]):
            continue
        else:
            c=dfs(used,c,ei)
    return c

ans=0
for i in range(m):
    a,b=eab[i]
    e[a].remove(b)
    e[b].remove(a)
    ci=dfs([False for _ in range(n+1)],0,1)
    if(ci!=n):
        ans+=1
    e[a].append(b)
    e[b].append(a)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

class UnionFind():
    # parentsは「要素が根の場合に"そのグループの要素数*(-1)"を格納するリスト」
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    # 要素xが属するgroupの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    # 要素xが属するgroupと要素yが属するgroupを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するgroupのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    # 要素x,yが同じgroupに属するかをTrueかFalseで返す
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するgroupに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # groupの数を返す
    def group_count(self):
        return len(self.roots())
    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = MI()
ab = LI(m)

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if j==i:
            pass
        else:
            a = ab[j][0] - 1
            b = ab[j][1] - 1
            uf.union(a,b)
    if uf.size(0)==n:
        pass
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
edge=[lmp() for i in range(m)]
ans=0
for _ in range(m):
    l=[[] for i in range(n+1)]
    que=deque()
    ch=[0]*(n+1)
    ch[0]=1
    for i in range(m):
        if i!=_:
            l[edge[i][0]].append(edge[i][1])
            l[edge[i][1]].append(edge[i][0])
    q=1
    que.append(l[q])
    ch[1]=1
    while len(que):
        q=que.pop()
        for j in range(len(q)):
            if ch[q[j]]==0:
                que.append(l[q[j]])
                ch[q[j]]=1
    b=0
    for k in range(n+1):
        if ch[k]==0:
            b=1
    if b==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(M)]

G = [set() for i in range(N)]

for a, b in ab:
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

ans = 0
for a, b in ab:
    a -= 1
    b -= 1
    q = collections.deque([0])
    r = [1]*N
    r[0] = 1
    while(q):
        x = q.popleft()
        for y in G[x]:
            if (x == a and y == b) or (x == b and y == a):
                continue
            else:
                if r[y]:
                    r[y] = 0
                    q.append(y)
    if sum(r) > 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import *

def bfs():
    q = deque([0])
    visited = [False]*N
    visited[0] = True
    
    while q:
        v = q.popleft()
        
        for nv in range(N):
            if G[v][nv]==1:
                if not visited[nv]:
                    visited[nv] = True
                    q.append(nv)
    
    return False in visited
    
N, M = map(int, input().split())
G = [[0]*N for _ in range(N)]
edges = []

for _ in range(M):
    a, b = map(int, input().split())
    G[a-1][b-1] = 1
    G[b-1][a-1] = 1
    edges.append((a-1, b-1))

ans = 0

for a, b in edges:
    G[a][b] = 0
    G[b][a] = 0
    
    if bfs():
        ans += 1
    
    G[a][b] = 1
    G[b][a] = 1

print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from copy import deepcopy

def check(a):
    dist = floyd_warshall(a)

    for i in dist:
        if float("inf") in i:
            return True
    return False

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

edge = [[float("inf") for i in range(N)] for j in range(N)]


ab = []
for _ in range(M):
    a,b = map(int,input().split())
    ab.append((a,b))
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

ans = 0
for a,b in ab:
    tmp = deepcopy(edge)
    tmp[a-1][b-1] = float("inf")
    tmp[b-1][a-1] = float("inf")

    if check(tmp):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

def resolve():
    N, M = LI()
    ab = [LI_() for _ in range(M)]

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if j!=i:
                uf.unite(ab[j][0], ab[j][1])
        if not uf.same(ab[i][0], ab[i][1]):
            ans += 1

    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def f(N, M, a, b, skip):
    uf = UnionFind(N)
    for i, (aa, bb) in enumerate(zip(a, b)):
        if i == skip:
            continue
        uf.union(aa-1, bb-1)
    return uf.size(0) != N

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    def g(skip):
        return f(N, M, a, b, skip)
    return sum(map(g, range(M)))
        


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, M, a, b))

# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[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.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False


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)

    for j in range(M):
        a, b = ab[j]
        if j != i:
            UF.unite(a-1, b-1)
    s = set()
    for j in range(N):
        s.add(UF.find(j))
    
    if len(s) > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

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

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def is_bridge(n, ab, i):
    uni = UnionFind(n)
    for j, val in enumerate(ab):
        if i == j:
            continue
        else:
            uni.Unite(val[0]-1, val[1]-1)
    if uni.Count(0) == n:
        return False
    else:
        return True


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

ret = 0

for i in range(m):
    if is_bridge(n, ab, i):
        ret += 1

print(ret)