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 typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(bb(n, m, g))


def bb(n: int, m: int, g: List[Tuple[int, int]]):
    ret = 0
    for i in range(m):
        v = set()
        w = [1]
        while w:
            now = w.pop()
            v.add(now)
            for j, node in enumerate(g):
                if j == i:
                    continue
                if node[0] == now and node[1] not in v:
                    w.append(node[1])
                elif node[1] == now and node[0] not in v:
                    w.append(node[0])
        if len(v) != n:
            ret += 1
    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

n, m = map(int, input().split())
am_bm = []
side_map = dict()
for i in range(m):
    ai, bi = map(int, input().split())
    if ai not in side_map:
        side_map[ai] = set()
        side_map[ai].add(bi)
    else:
        side_map[ai].add(bi)
    if bi not in side_map:
        side_map[bi] = set()
        side_map[bi].add(ai)
    else:
        side_map[bi].add(ai)
    am_bm.append((ai, bi))

counter = 0
for i in range(m):
    a, b = am_bm[i]
    q = queue.Queue()
    q.put(1)
    node_passed = set()
    node_passed.add(1)
    while not q.empty():
        a_tmp = q.get()
        for b_tmp in side_map[a_tmp]:
            if a_tmp == a and b_tmp == b or a_tmp == b and b_tmp == a:
                pass
            elif b_tmp not in node_passed:
                q.put(b_tmp)
                node_passed.add(b_tmp)
    if len(node_passed) == n:
        counter += 1
print(m - counter)

Submission status: Accepted

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

def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def unit(x, y):
    gx = find(x)
    gy = find(y)

    if gx == gy:
        return

    if root[gx] > root[gy]:
        gx, gy = gy, gx

    root[gx] += root[gy]
    root[gy] = gx

cnt = 0
for i in range(m):
    root = [-1] * n
    for j in range(m):
        if i == j:continue
        unit(AB[j][0]-1, AB[j][1]-1)
    roots = [i for i in root if i < 0]
    cnt += (len(roots) != 1)
print(cnt)

Submission status: Accepted

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

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

ans=0
for i in range(M):
    uf=UnionFind(N)
    for j in range(M):
        if i==j:
            continue
        a,b=ab[j]
        uf.union(a-1,b-1)
    ans+=(uf.group_count()>1)
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
graph=[]
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return
for i in range(M):
  a,b=map(int,input().split())
  graph.append((a-1,b-1))
bridge=0
from collections import Counter
for i in range(M):
  par=[i for i in range(N)]
  size=[1 for i in range(N)] 
  for j in range(M):
    if j!=i:
      union(graph[j][0],graph[j][1])
  if N not in size:
    bridge+=1
print(bridge)

Submission status: Accepted

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

class UnionFindPathCompression():
    def __init__(self, n:int):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

    def find(self, x:int) -> int:
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x:int, y:int):
        px = self.find(x)
        py = self.find(y)

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


n,m = map(int,input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    ufpc = UnionFindPathCompression(n)
    ab_copy = copy.deepcopy(ab)
    ab_copy.pop(i)
    for a,b in ab_copy:
        a,b = a-1,b-1
        ufpc.union(a,b)
    for i in range(n):
        ufpc.find(i)
    check = set(ufpc.parents)
    if len(check) != 1:
        ans += 1
print(ans)

Submission status: Accepted

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

class UnionFindPathCompression():
    def __init__(self, n:int):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

    def find(self, x:int) -> int:
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x:int, y:int):
        px = self.find(x)
        py = self.find(y)

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


n,m = map(int,input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
memo = 0
for i in range(m):
    ufpc = UnionFindPathCompression(n)
    ab_copy = copy.deepcopy(ab)
    ab_copy.pop(i)
    for a,b in ab_copy:
        a,b = a-1,b-1
        ufpc.union(a,b)
    for i in range(n):
        ufpc.find(i)
    check = set(ufpc.parents)
    if len(check)==1:
        memo += 1
print(m-memo)

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.size = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.size[x] = 1

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.size[x] > self.size[y]:
            self.p[y] = x
            self.size[x] += self.size[y]
        else:
            self.p[x] = y
            self.size[y] += self.size[x]
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

    def getSize(self, x):
        return self.size[ds.findSet(x)]

N, M = map(int, input().split())
A = []
B = []
for i in range(M):
    a, b = map(int, input().split())
    A += [a]
    B += [b]
ans = 0
for i in range(M):
    ds = DisjointSet(N+1)
    for j, (a, b) in enumerate(zip(A, B)):
        if i == j:
            continue
        ds.unite(a, b)
    if len(set([ds.findSet(j) for j in range(1, N+1)])) != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x


N,M = MI()
edges = [tuple(MI()) for _ in range(M)]

ans = 0
for i in range(M):
    U = UnionFind(N)
    for j in range(M):
        if j != i:
            a,b = edges[j]
            U.unite(a,b)
    x,y = edges[i]
    if not U.same_check(x,y):
        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()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
ans=0
for i in range(m):
    a=UnionFind(n)
    for j in range(m):
        if i==j:
            continue
        a.union(l[j][0]-1,l[j][1]-1)
    if a.group_count()==2:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())

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

    edge_set.add((a, b))

ans = 0
for a, b in edge_set:
    q = deque()
    q.append(0)
    visited = set()
    while q:
        p = q.popleft()
        if p in visited:
            continue
        visited.add(p)
        for np in edges[p]:
            if (p, np) == (a, b) or (np, p) == (a, b):
                continue
            q.append(np)
    if len(visited) != N:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
sys.setrecursionlimit(10**7)

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

def dfs(v,G):
    seen[v] = True
    for next_v in G[v]:
        if seen[next_v] == True:
             continue
        dfs(next_v,G)

bridge = 0
# 各辺を取り除く
for a,b in side:
    Gc = copy.deepcopy(G)
    Gc[a].remove(b)
    Gc[b].remove(a)
    seen = [False]*N
    cnt = 0
    # 連結成分のカウント
    for s in range(N):
        if seen[s] == True:
            continue
        cnt += 1
        dfs(s,Gc)
    # 連結成分が 2 個以上ならその辺は橋    
    if cnt>=2:
        bridge += 1
print(bridge)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
edges = [inpl() for _ in range(m)]
res = 0
for ind in range(m):
    e = [[] for _ in range(n)]
    for i,(a,b) in enumerate(edges):
        if i == ind: continue
        e[a-1].append(b-1)
        e[b-1].append(a-1)
    seen = [False]*n
    cnt = 0
    for i in range(n):
        if seen[i]: continue    
        q = deque([])
        q.append(i)
        cnt += 1
        while q:
            now = q.popleft()
            if seen[now]: continue
            seen[now] = True
            for nx in e[now]:
                if seen[nx]: continue
                q.append(nx)
    if cnt != 1:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
cnt = 0
for x in A:
    G = {i:[] for i in range(1,N+1)}
    for y in A:
        if y!=x:
            a,b = y
            G[a].append(b)
            G[b].append(a)
    hist = [0 for _ in range(N+1)]
    que = deque([1])
    hist[1] = 1
    while que:
        z = que.popleft()
        for w in G[z]:
            if hist[w]==0:
                que.append(w)
                hist[w]=1
    if sum(hist)<N:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return x
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

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

    edge.append([a,b])


ans=0
for j in range(m):
    #初期化 
    #根なら-size,子なら親の頂点
    par = [-1]*n
    cnt=0
    for p in range(m):
        if p==j:
            continue
    
        e=edge[p]
        unite(e[0],e[1])  
          
    for k in range(n):
        if par[k]<0:
            cnt+=1

    if cnt>=2:
        ans+=1
    
    

    


print(ans)

Submission status: Accepted

Solution code:
from _collections import deque
n,m=map(int,input().split())
ab=[[0,0] for i in range(m)]
for i in range(m):
    ab[i][0],ab[i][1]=map(int,input().split())
ans=0
for i in range(m):
    edg=[[] for j in range(n+1)]
    dep=[-1]*(n+1)
    dep[0]=1
    dep[1]=1
    for j in range(m):
        if j!=i:
            a,b=ab[j][0],ab[j][1]
            edg[a].append(b)
            edg[b].append(a)
    data=deque([1])
    while len(data)>0:
        p=data.popleft()
        for j in edg[p]:
            if dep[j]==-1:
                dep[j]=1
                data.append(j)
    if not all(dep[i]==1 for i in range(n+1)):ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.siz = n

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

  def unite(self, x, y):
    x = self.find_root(x)
    y = self.find_root(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.siz -= 1

  def root_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

  def count(self, x):
    return -self.n[self.find_root(x)]

  def size(self):
    return self.siz

n,m=map(int,input().split())
edges=[list(map(int,input().split()))for _ in range(m)]
ans=0
for i in range(m):
  u=UnionFind(n)
  for j in range(m):
    if j==i:continue
    a,b=edges[j]
    a-=1
    b-=1
    u.unite(a,b)
  if u.size()!=1:ans+=1
print(ans)

Submission status: Accepted

Solution code:
class DisjointSet:
    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 same(self, x, y):
        return self.find(x) == self.find(y)

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


N, M, *ab = map(int, open(0).read().split())
edges = [(a - 1, b - 1) for a, b in zip(*[iter(ab)] * 2)]

ans = 0
for i in range(M):
    ds = DisjointSet(N)
    for j in range(M):
        if i == j:
            continue
        ds.union(*edges[j])
    if len([-p for p in ds.parents if p < 0]) > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque
from copy import deepcopy

n,m=nii()
l=[lnii() for i in range(m)]

def BFS(t_l):
  tree=[[] for i in range(n)]
  for a,b in t_l:
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)

  dist=[-1 for i in range(n)]
  dist[0]=0

  que=deque()
  que.append(0)

  while que:
    x=que.popleft()
    for i in tree[x]:
      if dist[i]==-1:
        que.append(i)
        dist[i]=dist[x]+1

  return dist

ans=0
for i in range(m):
  t_l=deepcopy(l)
  del t_l[i]
  dist=BFS(t_l)
  if -1 in dist:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x


N,M = MI()
edges = [tuple(MI()) for _ in range(M)]

ans = 0
for i in range(M):
    U = UnionFind(N)
    for j in range(M):
        if j != i:
            a,b = edges[j]
            U.unite(a,b)
    x,y = edges[i]
    if not U.same_check(x,y):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
E = []
for _ in [0]*M:
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    E.append((a, b))


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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

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

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(E):
        if j == i:
            continue
        uf.unite(a, b)
    if uf.num_union() != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        x が属するグループを探索して親を出す。
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


N,M = map(int,input().split())
E = []
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  E.append((a,b))

ans = 0

for ng in range(M):
  uf = UnionFind(N)
  for i in range(M):
    if i == ng:
      continue
    else:
      uf.union(E[i][0],E[i][1])
  if uf.get_size(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)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * 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._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j,(a,b) in enumerate(AB):
        if i==j: continue
        a,b = a-1,b-1
        if uf.is_same(a,b): continue
        uf.unite(a,b)
    if uf.size(0) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

    def root(self, i):
        if self.parent[i] < 0:
            return i

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)

        if i == j:
            return

        if i > j:
            i, j = j, i

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, i):
        return -self.parent[self.root(i)]

    def roots(self):
        return [self.root(i) for i in range(self.N)]

    def groupcount(self):
        return len(set(self.roots()))

N, M = map(int, input().split())
edges = [[int(x) - 1 for x in input().split()] for _ in range(M)]

ans = 0

# 全てのedgeに対して
for i in range(M):
    # UnionFind木を初期化
    forest = UnionFind(N)

    # i番目のエッジを除いたものをつなぐ
    for i, j in edges[:i] + edges[i+1:]:
        forest.unite(i, j)

    # 全てのノードがつながっている <=> グループ数は1
    # グループ数（島の数）が１ではない <=> グラフは２つ以上の島から成る
    if forest.groupcount() != 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


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

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


def main():
    ans = 0

    for b in bridge:
        seen = [0] * N
        seen[0] = 1
        
        # BFS
        que = deque([0])
        while que:
            v = que.popleft()
            for nv in to[v]:
                if set([v, nv]) == b:
                    continue
                if not seen[nv]:
                    seen[nv] = 1
                    que.append(nv)

        if seen != [1] * N:
            ans += 1
    print(ans)


if __name__ == "__main__":
    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 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 = map(int, input().split())
    G = []
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G.append((a,b))
    ans = 0
    for i in range(M):
        uni = UnionFind(N)
        for j in range(M):
            if i == j:
                continue
            uni.union(G[j][0],G[j][1])
        if uni.group_count() >= 2:
            ans += 1

    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
ab=[[0,0]  for i in range(m)]
for i in range(m):
    ab[i][0],ab[i][1]=map(int,input().split())
ans=0
for i in range(m):
    root=[j for j in range(n+1)]
    root[0]=1
    def r(x):
        if root[x]==x:
            return x
        else:
            root[x]=r(root[x])
            return root[x]
    def unite(x,y):
        x=r(x)
        y=r(y)
        if x==y:
            return
        else:
            x,y=min(x,y),max(x,y)

            root[y]=x
    for j in range(m):
        if j!=i:
            a,b=ab[j][0],ab[j][1]
            unite(a,b)

    if not all(r(j)==1 for j in range(1,n+1)):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from _collections import deque
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
ab=[[0,0]  for i in range(m)]
for i in range(m):
    ab[i][0],ab[i][1]=map(int,input().split())
ans=0
for i in range(m):
    edg=[[] for j in range(n+1)]
    for j in range(m):
        if j!=i:
            a,b=ab[j][0],ab[j][1]
            edg[a].append(b)
            edg[b].append(a)
    che=[0]*(n+1)
    che[0]=1
    def search(x):
        che[x]=1
        for j in edg[x]:
            if che[j]==0:
                search(j)
    search(1)
    if not all(che[j]==1 for j in range(n+1)):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from _collections import deque
n,m=map(int,input().split())
ab=[[0,0]  for i in range(m)]
for i in range(m):
    ab[i][0],ab[i][1]=map(int,input().split())
ans=0
for i in range(m):
    edg=[[] for j in range(n+1)]
    for j in range(m):
        if j!=i:
            a,b=ab[j][0],ab[j][1]
            edg[a].append(b)
            edg[b].append(a)
    che=[0]*(n+1)
    che[0]=1
    data=deque([1])
    while len(data)>0:
        p=data.popleft()
        che[p]=1
        for j in range(len(edg[p])):
            r=edg[p][j]
            if che[r]==0:
                data.append(r)
                che[r]=1
    if not all(che[j]==1 for j in range(n+1)):
        ans+=1
print(ans)