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:
N, M = map(int, input().split())
G = [[0 for j in range(N)] for i in range(N)]


def dfs(u):
    if is_visited[u]:
        return
    is_visited[u] = 1
    for i in range(N):
        if G[u][i]:
            dfs(i)


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

ans = 0

# print(G)
# print(A, B)
for i in range(M):
    is_visited = [0] * N
    a, b = A[i], B[i]
    G[a][b] = 0
    G[b][a] = 0
    dfs(0)
    # print(is_visited)
    if is_visited.count(1) != N:
        ans += 1
    G[a][b] = 1
    G[b][a] = 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n: int):
        self.__n = n
        self.__par = list(range(self.__n))
        self.__size = [1 for _ in range(self.__n)]

    def root(self, x: int) -> int:
        if self.__par[x] == x:
            return x
        self.__par[x] = self.root(self.__par[x])
        return self.__par[x]

    def merge(self, x: int, y: int) -> bool:
        rx, ry = self.root(x), self.root(y)
        if rx == ry: return False

        if self.__size[rx] < self.__size[ry]:
            rx, ry = ry, rx

        self.__size[rx] += self.__size[ry]
        self.__par[ry] = rx
        return True

    def check(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        return self.__size[self.root(x)]


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

ans = 0
for i in range(M):
    uf = UnionFind(N + 1)
    for j in range(M):
        if i == j: continue
        a, b = ABm[j]
        uf.merge(a, b)

    if uf.size(1) != N:
        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

        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()}

N, M = map(int, input().split())
def int_(num):
    return int(num) - 1
ablist = [list(map(int_, input().split())) for _ in range(M)]
ans = 0
for ng in range(M):
    uf = UnionFind(N)
    for i in range(M):
        if i != ng:
            uf.union(*ablist[i])
    if uf.group_count() != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
from collections import deque
aa = [0] * M
bb = [0] * M
ans = 0
for i in range(M):
    a,b = [int(j) for j in input().split()]
    graph[a].append(b)
    graph[b].append(a)
    aa[i] = a
    bb[i] = b
import copy
grapha = copy.deepcopy(graph)
for k in range(M):
    graph[aa[k]].remove(bb[k])
    graph[bb[k]].remove(aa[k])
    seen = [False] * (N+1)
    from collections import deque
    que = deque()
    que.append(1)
    while len(que) != 0:
        x = que.popleft()
        seen[x] = True
        for i in graph[x]:
            if seen[i]:
                continue
            que.append(i)
            seen[i] = True
    for l in range(1,N+1):
        if seen[l]:
            continue
        ans +=1
        break
    graph = copy.deepcopy(grapha)
print(ans)

Submission status: Accepted

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

def dfs(con, v, mat):
  if con[v] == 1:
    return
  con[v] = 1
  for x in mat[v]:
    dfs(con, x, mat)
  
def is_connected(n, mat):
  con = [0] * n
  dfs(con, 0, mat)
  return sum(con) == n
  
ans = 0
for i in range(m):
  mat = [[] for _ in range(n)]
  for j in range(m):
    if j == i:
      continue
    mat[e[j][0]] += [e[j][1]]
    mat[e[j][1]] += [e[j][0]]
  if not is_connected(n, mat):
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict

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

AB = []
G = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    AB.append([a, b])
    G[a].append(b)
    G[b].append(a)

ans = 0
for a, b in AB:
    memo = [0]*(n+1)
    memo[a] = 1
    que = [c for c in G[a] if c != b]
    while que:
        c = que.pop()
        memo[c] = 1
        for nc in G[c]:
            if memo[nc] == 0:
                que.append(nc)
    if np.count_nonzero(memo) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
A=[[0]*2 for i in range(m)]
for i in range(m):
  A[i]=list(map(int,input().split()))
ans=0
for i in range(m):
  B=[[] for i in range(n)]
  for j in range(m):
    if j==i:
      continue
    B[A[j][0]-1].append(A[j][1]-1)
    B[A[j][1]-1].append(A[j][0]-1)
  C=[0]*n
  C[0]=1
  D=deque([0])
  while len(D)>0:
    x=D[0]
    D.popleft()
    for j in range(len(B[x])):
      if C[B[x][j]]==0:
        D.append(B[x][j])
        C[B[x][j]]=1
  if C!=[1]*n:
    ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
'''
無向グラフの橋の数を調べる
ループ無し/2重辺無し
'''

def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    node,m =map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(m)]
    res = 0

    def dfs(num):
        flag[num-1] = 1
        for x, y in edge:
            if x==num:
                if not flag[y-1]:
                    dfs(y)
            if y==num:
                if not flag[x-1]:
                    dfs(x)
    
    for i in range(m):
        bridge = edge.pop(i)
        flag = [0]*node
        s = edge[0][0]
        dfs(s)
        if not all(flag):
            res += 1
        edge.insert(i, bridge)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    node,m =map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(m)]
    res = 0

    def dfs(num):
        for x, y in edge:
            if x==num:
                if not flag[y-1]:
                    flag[y-1] = 1
                    dfs(y)
            if y==num:
                if not flag[x-1]:
                    flag[x-1] = 1
                    dfs(x)
    
    for i in range(m):
        bridge = edge.pop(i)
        flag = [0]*node
        s = edge[0][0]
        flag[s-1]=1
        dfs(s)
        if not all(flag):
            res += 1
        edge.insert(i, bridge)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import copy

def main():
    mod=10**9+7
    N,M=MI()
    inf=1000
    D=[[inf]*N for _ in range(N)]
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        D[a][b]=1
        D[b][a]=1
        
    for i in range(N):
        D[i][i]=0
        
    def warshall_floyd(d):
        #d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
           
        for i in range(N):
            for j in range(N):
                if d[i][j]==inf:
                    return True
        return False
    cnt=0 
    for i in range(N):
        for j in range(i,N):
            if D[i][j]==1:
                d=copy.deepcopy(D)
                d[i][j]=inf
                d[j][i]=inf
                if warshall_floyd(d):
                    cnt+=1
                    
    print(cnt)
    
    



main()

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 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 size(self, x):
        return -self.parents[self.find(x)]

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

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

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j: continue
        uf.unite(edge[j][0], edge[j][1])
    ans += (len(uf.roots()) != 1)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

# 隣接行列
graph = [[0] * (N + 1) for _ in range(N + 1)]

for i, j in edge:
  graph[i][j] = 1
  
ans = 0
INF = 10 ** 9
for a, b in edge:
  # 辺を取り除く-> INF
  graph[a][b] = INF
  dist = dijkstra(graph, indices=a, directed=False) # directed=False -> 無効グラフ用
  if dist[b] >= INF:
    ans += 1
  # 元に戻す -> 1
  graph[a][b] = 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
P = [list(map(int,input().split())) for k in range(M)]
ans = 0

for i in range(M):
    T = P[:i]+P[i+1:]
    G = [[] for k in range(N)]
    V = [0 for k in range(N)]
    for e in T:
        G[e[0]-1].append(e[1]-1)
        G[e[1]-1].append(e[0]-1)

    def dfs(visited,graph,ima):
        for e in graph[ima]:
            if visited[e] == 0:
                visited[e] = 1
                dfs(visited,graph,e)
    dfs(V,G,0)
    if sum(V) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
L = [[0, 0] for _ in range(m)]
g = [[] for _ in range(n)]
for j in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    L[j][0] = a
    L[j][1] = b

from collections import deque

ans = 0
for i in range(m):
    g = [[] for _ in range(n)]
    for j in range(m):
        if j == i:
            continue
        a = L[j][0]
        b = L[j][1]
        g[a].append(b)
        g[b].append(a)
    #print(g)
    s = deque()
    s.append(0)
    visit = [-1]*n
    visit[0] = 0
    while s:
        x = s.pop()
        for new_x in g[x]:
            if visit[new_x] == -1:
                visit[new_x] = visit[x] + 1
                s.append(new_x)
    if min(visit) == -1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
E = [[False for i in range(N)] for j in range(N)]

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

# 葉のindexを取得
def search_leaf(edge_list):
    for i in range(N):
        if edge_list[i].count(True) == 1:
            return i
    return -1

ans = 0
for _ in range(M):
    V = search_leaf(E)
    if V == -1: 
        break
    
    # 橋を壊す
    main_land = E[V].index(True)
    E[V][main_land] = E[main_land][V] = False

    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
AB = []
edge = np.zeros((N, N), dtype=int)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    AB.append((a, b))
    edge[a][b] = 1
    edge[b][a] = 1

ans = 0
for i in range(M):
    graph = np.copy(edge)
    a, b = AB[i]
    graph[a][b] = 0
    graph[b][a] = 0
    fw = floyd_warshall(graph)
    if fw.max() > 10000:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    matrix = [[False]*N for _ in range(N)]
    AB=LLIN_(M)
    for a,b in AB:
        matrix[a][b] = True
        matrix[b][a] = True
    def is_bridge():
        q = [0]
        visited = set()
        while q:
            v = q.pop()
            if v in visited:
                continue
            visited.add(v)
            for to in range(N):
                if matrix[v][to]:
                    if to in visited:
                        continue
                    q.append(to)
        return len(visited) < N
    ans = 0
    for a,b in AB:
        matrix[a][b] = False
        matrix[b][a] = False
        if is_bridge():
            ans += 1
        matrix[a][b] = True
        matrix[b][a] = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def dfs(v, e):
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                if (next_v, u) == e or (u, next_v) == e:
                    continue  # 使用禁止
                seen[next_v] = True
                todo.append(next_v)
                break
            else:
                todo.pop()
    ans = 0
    for e in edges:
        seen = [False] * N
        dfs(0, e)
        if not(all(seen)):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def check(Edge, e, N):
    q = deque()
    visited = [False] * N
    for nextNode in Edge[0]:
        if (0, nextNode) != e: q.append((0, nextNode))
    visited[0] = True
    while q:
        preNode, nowNode = q.popleft()
        if not visited[nowNode]:
            visited[nowNode] = True
            for nextNode in Edge[nowNode]:
                if nextNode == preNode: continue
                if (min(nowNode, nextNode), max(nowNode, nextNode)) != e:
                    q.append((nowNode, nextNode))
    return False in visited


def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    EdgeN = [None] * M
    for i in range(M):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
        EdgeN[i] = (min(a-1, b-1), max(a-1, b-1))
    count = 0
    for e in EdgeN:
        if check(Edge, e, N): count += 1
    print(count)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0

for i in range(M):
    uf = Unionfind(N)
    
    for j in range(M):
        if j==i:
            continue
        
        a, b = ab[j][0], ab[j][1]
        uf.unite(a-1, b-1)
    
    if uf.count(0)!=N:
        ans += 1

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

ans = 0
for a,b in AB:
    a,b = a-1,b-1
    uf = UnionFind(N)
    for u,v in AB:
        u,v = u-1,v-1
        if u==a and v==b: continue
        if uf.is_same(u,v): continue
        uf.unite(u,v)
    if not uf.is_same(a,b):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1


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

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        
        uf.unite(es[j][0], es[j][1])

    # 外した辺の両端が同じUnionでなければそれは橋
    if not uf.is_same(es[i][0], es[i][1]):
        ans += 1
        

print(ans)

Submission status: Accepted

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

    
ans=0




def dfs(start,finish):
    global ans
    finish.add(start)#もう訪れたところ
   # print(finish)
    if len(finish)==n:#全部回ってたら終了
        ans+=1#橋じゃない数
        return 
    for i in adlist[start-1]:

        if i not in finish:#通ったところに入っていないなら通れるということ   
            dfs(i,finish)

for i in range(m):
    adlist=[]
    for h in range(n):    
        adlist.append([])
    for j in range(m):
        if i!=j:
            x=ab[j][0]
            y=ab[j][1]
            adlist[x-1].append(y)
            adlist[y-1].append(x)
    finish=set()
    #print(adlist)
    dfs(1,finish)#引数がけすノード
#print(adlist)

print(m-ans)

"""
iのノードを消したときすべてのところを回れるかというう動作をn回繰り返す
こればつ
ノードを消していたから違う線を消さなければならない
だからそれぞれのはしがないと金の隣接リストを作らないイケナイ
"""

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
        if self.parents[y] < self.parents[x]:
            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 solve():
    N, M = map(int, input().split())
    a, b = [0] * M, [0] * M
    for i in range(M):
        a[i], b[i] = map(lambda x: int(x) - 1, input().split())
    
    ans = 0
    for i in range(M):
        uf_tree = UnionFind(N)
        for j in range(M):
            if i == j:
                continue
            
            uf_tree.union(a[j], b[j])
        if 1 < uf_tree.group_count():
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#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 main():
    N,M = list(map(int,input().split()))
    ab = [list(map(int,input().split())) for i in range(M)]
    
    uf = UnionFind(N+1)
    for i in range(M):
        uf.union(ab[i][0],ab[i][1])
    base = uf.group_count()
    
    ans = 0
    for skip in range(M):
        uf = UnionFind(N+1)
        for i in range(M):
            if skip == i:
                continue
            else:
                uf.union(ab[i][0],ab[i][1])
        if uf.group_count()-base == 1:
            ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(bri1): #始点入力
    for l in land[bri1-1]:
        if seen[l-1] == 0 and not (bri1==bri[0] and l==bri[1]):
            seen[l-1] = 1
            dfs(l)

N,M = map(int,input().split())
data = [0]*M
land = [[] for i in range(N)] #i+1番目の島とつながっているところ
for i in range(M):
    a,b = map(int,input().split())
    data[i] = [a,b]
    land[a-1].append(b)
    land[b-1].append(a)

cnt = 0
for i in range(M):
    bri = data[i]
    seen = [0]*N
    dfs(bri[0])
    if sum(seen) != N:
        cnt += 1

print(cnt)

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 unite(self,x,y): #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):#xとyが同じグループにいるか判定
        return self.find(x)==self.find(y)
    
    def members(self,x):#xと同じグループのメンバーを列挙
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    
    def size(self,x):#xが属するグループのメンバーの数
        return -self.parents[self.find(x)]
    
    def roots(self):#ufの根を列挙
        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):#print()での表示用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    import sys
    input=sys.stdin.readline
    n,m=map(int,input().split())
    edges=[0]*m
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        edges[i]=[a,b]
    
    cnt=0
    for i in range(m):
        uf=UnionFind(n)
        for j in range(m):
            if i!=j:
                uf.unite(edges[j][0],edges[j][1])
        if uf.size(0)!=n:
            cnt+=1
    print(cnt)   
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(i,prohi,visited,edges,before=-1): 
    if visited[i]:
        cnt=1
        visited[i]=False
        for e in edges[i]:
            if e[1]!=prohi and e[0]!=before:
                cnt+=dfs(e[0],prohi,visited,edges,i)
        return cnt

    else:
        return 0

def main():
    import sys
    input=sys.stdin.readline
    n,m=map(int,input().split())
    edges=[[] for i in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        edges[a].append([b,i])
        edges[b].append([a,i])
    
    ans=0
    for prohi in range(m):
        cnt=0
        visited=[True]*n
        if dfs(0,prohi,visited,edges)!=n:
            ans+=1
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m = map(int, input().split())
link = []
for i in range(m):
    tmp = list(map(int,input().split()))
    link.append(tmp)

ans=0
for bri in range(m):
    wf=[[10**10 for i in range(n)] for j in range(n)]
    for i in range(m):
        if i==bri:
            continue
        a=link[i][0]
        b=link[i][1]
        wf[a-1][b-1] = 1
        wf[b-1][a-1] = 1

    for i in range(n):
        wf[i][i]=0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j],wf[i][k]+wf[k][j])

    is_b=True
    for i in range(n):
        for j in range(n):
            if wf[i][j] == 10**10:
                is_b=False
                break
    if not is_b:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s,target):
    inf=float("inf")
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]
    M=[[] for _ in range(n)]
    for i in AB:
        if i==target:continue
        a,b=i[0]-1,i[1]-1
        M[a] +=[b]
        M[b] +=[a]

    color[s]="gray"
    D[s]=0
    queue=deque([s])

    while len(queue)!=0:
        u=queue.popleft()
        color[u]="gray"
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return True if any([i==inf for i in D]) else False


n,m=map(int,input().split())
AB=[tuple(map(int,input().split())) for _ in range(m)]

cnt=0
for i in range(m):
    cnt +=BFS(0,AB[i])
print(cnt)