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())
AB = []
ans = 0

for _ in range(M):
    Ai, Bi = map(int, input().split())
    AB.append((Ai,Bi))

for i in range(M):
    memo = [[] for _ in range(N+1)]
    for j in range(M):
        if i != j:
            memo[AB[j][0]].append(AB[j][1])
            memo[AB[j][1]].append(AB[j][0])
    queue = [1]
    visited = [0] * (N+1)

    while queue:
        node = queue.pop()
        next_nodes = memo[node]
        for next_node in next_nodes:
            if visited[next_node] == 0:
                queue.append(next_node)
        visited[node] = 1

    if sum(visited[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)]

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

for i in range(m):
    a,b=map(int,input().split())
    e.append((a-1,b-1))
    
for i in range(m):
    uf = UnionFind(n)
    for a,b in e[:i]+e[i+1:]:
        uf.union(a,b)
    if uf.size(0) < n:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

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

def DFS(m):
  t_l=deepcopy(l)
  del t_l[m]

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

  seen=set()
  seen.add(0)

  dq=deque()
  dq.append(0)

  while dq:
    x=dq.pop()
    for i in tree[x]:
      if i not in seen:
        dq.append(i)
        seen.add(i)

  return seen

ans=0
for i in range(m):
  st=DFS(i)
  if len(st)!=n:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

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

def BFS(m):
  t_l=deepcopy(l)
  del t_l[m]

  tree=[[] for j 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

  global ans
  if -1 in dist:
    ans+=1

ans=0
for i in range(m):
  BFS(i)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

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

def BFS(m):
  t_l=deepcopy(l)
  del t_l[m]

  tree=[[] for j 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):
  d=BFS(i)
  if -1 in d:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    array = [[] for _ in range(n+1)]
    temp = []
    for _ in range(m):
        a, b = map(int, input().split())
        array[a].append(b)
        array[b].append(a)
        temp.append([a, b])
    result = 0
    from collections import deque
    while len(temp) > 0:
        a, b = temp.pop()
        array[a].remove(b)
        array[b].remove(a)
        d = deque([1])
        pop = d.pop
        append = d.append
        flag = [True] * (n + 1)
        while len(d) > 0:
            now = pop()
            for to in array[now]:
                if flag[to]:
                    append(to)
                    flag[to] = False
        for f in flag[1:]:
            if f:
                result += 1
                break
        array[a].append(b)
        array[b].append(a)
    print(result)
main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    array = [[] for _ in range(n+1)]
    temp = []
    for _ in range(m):
        a, b = map(int, input().split())
        array[a].append(b)
        array[b].append(a)
        temp.append([a, b])
    result = 0
    from collections import deque
    while len(temp) > 0:
        a, b = temp.pop()
        array[a].remove(b)
        array[b].remove(a)
        d = deque([1])
        pop = d.popleft
        append = d.append
        flag = [True] * (n + 1)
        while len(d) > 0:
            now = pop()
            for to in array[now]:
                if flag[to]:
                    append(to)
                    flag[to] = False
        for f in flag[1:]:
            if f:
                result += 1
                break
        array[a].append(b)
        array[b].append(a)
    print(result)
main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from collections import deque
n,m=map(int,input().split())
matrix=[[0]*n]*n
matrix=np.array(matrix)
l=deque()
for _ in range(m):
    a,b=map(int,input().split())
    l.append([a,b])
    matrix[a-1][b-1]=1
count=0
for i in range(m):
    [a,b]=l.popleft()
    matrix[a-1][b-1]=0
    k,kk=connected_components(matrix)
    if kk[a-1]!=kk[b-1]:
        count+=1
    l.append([a,b])
    matrix[a-1][b-1]=1
print(count)

Submission status: Accepted

Solution code:
from collections import deque

def check(st,en,ed):
    ed[st-1][en-1] -= 1
    ed[en-1][st-1] -= 1
    cnt = [0] * n
    q = deque()
    q.append(st)
    cnt[st-1] += 1
    while q:
        now = q.popleft()
        if ed[now-1][en-1] == 1:
            ed[st-1][en-1] += 1
            ed[en-1][st-1] += 1
            return False
        for r in range(n):
            if ed[now-1][r] == 1 and cnt[r] == 0:
                q.append(r+1)
                cnt[r] += 1
    ed[st-1][en-1] += 1
    ed[en-1][st-1] += 1
    return True

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

edge = [[0] * n for _ in range(n)] 

nodes = []

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

ans = 0 
for node in nodes:
    a,b = node[0], node[1]
    if check(a,b,edge):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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, *AB = map(int, read().split())
A = AB[::2]
B = AB[1::2]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(zip(A, B)):
        if i != j:
            uf.union(a - 1, b - 1)
    if uf.group_count() > 1:
        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())
graph = [list(map(int,input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
            uf.union(graph[j][0]-1, graph[j][1]-1)
    if uf.group_count() != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    frag = set([S])
    que = deque([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:
            if i not in frag:
                que.append(i)
                frag.add(i)

    ans = 1
    if len(frag) == N:
        ans = 0
    return ans


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

near = [set([]) for _ in range(n)]
for i, j in ab:
    near[i - 1].add(j - 1)
    near[j - 1].add(i - 1)

cnt = 0
for i, j in ab:
    near[i - 1].remove(j - 1)
    near[j - 1].remove(i - 1)
    cnt += bfs(near,1,n)
    near[i - 1].add(j - 1)
    near[j - 1].add(i - 1)
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    dist = [-1 for _ in range(N)]
    pas = [-1 for _ in range(N)]
    dist[S], pas[S] = 0, 's'
    frag = set([S])
    que = deque([S])

    while len(que) > 0:
        q = que.popleft()
        near = NEAR[q]
        for i in near:
            if i in frag:
                continue
            que.append(i)
            frag.add(i)

    ans = 1
    if len(frag) == N:
        ans = 0
    return ans


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

near = [set([]) for _ in range(n)]
for i, j in ab:
    near[i - 1].add(j - 1)
    near[j - 1].add(i - 1)

cnt = 0
for i, j in ab:
    near[i - 1].remove(j - 1)
    near[j - 1].remove(i - 1)
    cnt += bfs(near,1,n)
    near[i - 1].add(j - 1)
    near[j - 1].add(i - 1)
print(cnt)

Submission status: Accepted

Solution code:
# import sys
# import math
# import itertools
# from collections import deque
# from collections import defaultdict
# import heapq
# import copy
# import bisect
# import numpy as np
# from scipy.special import comb

# def my_input(): return sys.stdin.readline().rstrip()

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

    a = [0] * M
    b = [0] * M
    for i in range(M):
        a[i], b[i] = map(int, input().split())

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#2311
#import numpy as np

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=MI()
	li=[]
	for _ in range(m):
		a,b=MI()
		a-=1
		b-=1
		li.append([a,b])
	#print(li)

	ans=0

	for i in range(m):
		UF=UnionFind(n)
		for j in range(m):
			if i==j:
				continue
			UF.union(li[j][0],li[j][1])
		ans+=(UF.group_count()==1)
	print(m-ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

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

from collections import defaultdict
from collections import deque
d=defaultdict(list)
for l in L:
    d[l[0]-1].append(l[1]-1)
    d[l[1]-1].append(l[0]-1)

#print(d)

# 辺を切断した状態で幅優先探索をしてすべての頂点に行けるか
def check_path(hen):
        
    visit=[False]*n
    q=deque([0])
    
#    print('L=',L)
#    print('hen=',hen)
    
    while q:
        node = q.popleft()
#        print('current->', node)
        visit[node]=True
        Nexts = d[node]
        for nxt in Nexts:
            if visit[nxt]:
#                print(nxt, ' is already visited.')
                continue
            
            if node+1 not in L[hen] or nxt+1 not in L[hen]:
#                print('next->', nxt)
                q.append(nxt)
    
#    print('visit=', visit)
    return all(visit)
    
cnt=0
for i in range(m):
    if not check_path(i):
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
import collections
def bfs(start):
    d = [-1]*n
    d[start] = 0
    q = collections.deque([start])
    while q:
        c = q.popleft()
        next_v = edge[c] 
        for v in next_v:
            if d[v] == -1:
                q.append(v)
                d[v] = d[c] + 1
    return d

n,m = map(int,input().split())
koho = []
edge = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    koho.append([a,b])
    edge[a].append(b)
    edge[b].append(a)
cnt = 0
for i in range(m):
    edge = [[] for _ in range(n)]
    for j in range(m):
        if i == j:
            continue
        edge[koho[j][0]].append(koho[j][1])
        edge[koho[j][1]].append(koho[j][0])
    a = bfs(0)
    flag = 0
    for j in a:
        if j == -1:
            flag = 1
    if flag == 1:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import copy
from collections import deque

n , m = map(int,input().split())
route = [[] for i in range(n+1)]
nuku = []
for i in range(m):
    a , b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
    nuku.append([a,b])
ans = 0
for a , b in nuku:
    kari = copy.deepcopy(route)
    kari[a].remove(b)
    kari[b].remove(a)
    d = deque()
    d.append(1)
    tansaku = [True for i in range(n+1)]
    cou = 0
    tansaku[1] = False
    while d:
        cou += 1
        now = d.popleft()
        for k in kari[now]:
            if tansaku[k]:
                tansaku[k] = False
                d.append(k)
    if cou != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
graph = {i:[] for i in range(1,n+1)}

for _ in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
  
bridge = set([])

ans = 0
while 1:
  count = 0
  for i in range(1,n+1):
    if len(graph[i]) == 1:
      count += 1
      a = graph[i][0]
      graph[a].remove(i)
      graph[i] = []
  ans += count
  if count == 0:
    break
  else:
    count = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n, m = MII()
    ab = [MIIZ() for _ in range(m)]
    cnt = 0
    for i in range(m):
        graph = [[] for _ in range(n)]
        for k,(a,b) in enumerate(ab):
            if i == k: continue
            graph[a].append(b)
            graph[b].append(a)
        dist = [-1]*n
        dq = deque()
        dist[0] = 0
        dq.append(0)
        while dq:
            v = dq.popleft()
            for nv in graph[v]:
                if dist[nv] != -1: continue
                dist[nv] = dist[v] + 1
                dq.append(nv)
        if -1 in dist:
            cnt += 1
    print(cnt)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[] for _ in range(n+1)]
eab=[]
for i in range(m):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    eab.append([a-1,b-1])
 
def dfs(visited,count,node):
    visited[node]=True
    count+=1
    ev=edge[node]
    for node in ev:
        if visited[node]:
            continue
        else:
            count=dfs(visited,count,node)
    return count

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

Submission status: Accepted

Solution code:
from collections import deque
 
def dfs(n, start, graph):
  visited = [False] * n
  stack = deque()
  stack.append(start)
  visited[start] = True
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited
 
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
 
ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)
 
  if not all(dfs(n, 0, graph)):
    ans += 1
print(ans)

Submission status: Accepted

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


def dfs(curr):
    visit[curr] = 1
    for x in graph[curr]:
        if visit[x] == 0:
            dfs(x)


ans = 0
for i in range(m):
    temp = ab[:i] + ab[i + 1:]
    graph = [[] for _ in range(n + 1)]
    for a, b in temp:
        graph[a].append(b)
        graph[b].append(a)

    visit = [0] * (n + 1)
    dfs(1)

    if sum(visit[1:]) != n:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parents[x] == x:
            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.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m = map(int,input().split())
A = [0]*m
B = [0]*m
for i in range(m):
    A[i],B[i] = map(int,input().split())

ans = 0
for i in range(m):
    u = UnionFind(n)
    for j in range(m):
        if i==j:continue
        a,b = A[j]-1,B[j]-1
        u.union(a,b)
    for j in range(n):
        u.find(j)
    if len(set(u.parents))!=1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    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 check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        # rankの小さいものを大きいほうにくっつける
        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 count_group(self, n):
        return len({self.find(x) for x in range(1, n + 1)})

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

cnt = 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, b)

    if uf.count_group(n) != 1:cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

from collections import deque
def dfs(G, a, b):
    #(a, b)は除外する辺
    q=deque()
    q.append((1, -1, 0))
    log = [0] * n
    log[0] = 1
    while q:
        V,P,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            #q.append((V,P,1))
            for new_v in G[V-1]:
                if {a, b} == {new_v, V}:continue
                if new_v==P:continue
                if log[new_v - 1]:continue
                log[new_v - 1] = 1
                q.append((new_v,V,0))

    return sum(log) != n

n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)
'''
ab一個を除いた時に連結かどうか調べる
'''

ans = 0
for a, b in ab:
    if dfs(G, a, b):ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n, m = na()
ab = nan(m)

g = [[] for _ in range(n)]
for i in range(m):
    a, b = ab[i]
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

def bfs(va, vb):
    q = deque()
    q.append((0, 0))
    dist = [-1] * n
    while len(q):
        p, d = q.popleft()
        if dist[p] != -1:
            continue
        dist[p] = d
        for nv in g[p]:
            if (p == va and nv == vb) or (p == vb and nv == va):
                continue
            q.append((nv, dist[p] + 1))
    
    for i in range(n):
        if dist[i] == -1:
            return 1
    return 0

proc = [False] * n
def dfs(v, p):
    if proc[v]:
        return 0
    proc[v] = True
    res = 0
    for nv in g[v]:
        if nv == p:
            continue
        res += bfs(nv, v)
        res += dfs(nv, v)
    return res

print(dfs(0, -1))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    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 check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        # rankの小さいものを大きいほうにくっつける
        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 count_group(self, n):
        return len({self.find(x) for x in range(1, n + 1)})

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

cnt = 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, b)

    if uf.count_group(n) != 1:cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import copy

# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[y] = x
    return True


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


def size(x):
    return -par[find(x)]


N, M = map(int, input().split())
Road = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    Roadi = copy.deepcopy(Road)
    par = [-1] * N
    for j, r in enumerate(Road):
        if i == j:
            continue
        ra, rb = r
        ra -= 1
        rb -= 1
        unite(ra, rb)
    if par.count(-1) > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# C - Bridge
# https://atcoder.jp/contests/abc075/tasks/abc075_c

from collections import deque

def dfs(n, start, graph):
  visited = [False] * n
  stack = deque()
  stack.append(start)
  visited[start] = True
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited

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

ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)

  if not all(dfs(n, 0, graph)):
    ans += 1

print(ans)