Problem:


Score : 300 points

Problem Statement

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

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

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

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

Notes

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

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

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

Constraints

2 \leq N \leq 50

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

1 \leq a_i<b_i \leq N

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

The given graph is connected.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

Output

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

Sample Input 1

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

Sample Output 1

4

The figure below shows the given graph:

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

Sample Input 2

3 3
1 2
1 3
2 3

Sample Output 2

0

It is possible that there is no bridge.

Sample Input 3

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

Sample Output 3

5

It is possible that every edge is a bridge.



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


Sample output:
4

Submission status: Accepted

Solution code:
from collections import deque


class UnionFind:
    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


N, M = map(int, input().split(' '))
edges = [tuple(map(int, input().split(' '))) for _ in range(M)]

bridges = 0
for a1, b1 in edges:
    union_find = UnionFind(N)
    for a2, b2 in edges:
        if a1 == a2 and b1 == b2:
            continue
        union_find.union(a2, b2)
    if not union_find.find(a1, b1):
        bridges += 1

print(bridges)

Submission status: Accepted

Solution code:
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        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())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n
count = 0
graph = []
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph.append([x,y])
for i in range(m):
    p = [j for j in range(n)]
    par = [-1]*n
    for j in range(m):
        if i != j:
            unite(graph[j][0],graph[j][1])
    if not((-1)*n in par):
        count+=1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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), *q = [list(map(int, i.split())) for i in open(0)]
c = 0
for i in range(m):
    UF = UnionFind(n)
    for j, (a, b) in enumerate(q):
        if i == j:
            continue
        UF.union(a - 1, b - 1)
    if UF.group_count() > 1:
        c += 1
print(c)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
ans = 0
for i in range(M):
  uf = UnionFind(N)
  for j, (a, b) in enumerate(ab):
    if i == j:
      continue
    uf.union(a-1, b-1)
  root = set([uf.find(j) for j in range(N)])
  if len(root) >= 2:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def DFS(i,a,b):
    if i not in done:
        done.append(i)
        for f in g[i]:
            if [i,f]==[a,b] or [i,f]==[b,a]:
                continue
            else:
                DFS(f,a,b)
    else:
        return

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

ans=0
for i in range(M):
    done=[]
    DFS(0,edge[i][0],edge[i][1])
    if len(done)<N:
        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(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

from collections import defaultdict
import collections

res = 0
for i in range(m):
    abc = ab.copy()
    del abc[i]
    V = defaultdict(list)

    for _ in range(m-1):
        a, b = abc[_][0],abc[_][1]
        V[a].append(b)
        V[b].append(a)
    d1 =dfs(1)
    c = collections.Counter(d1)
    if c[-1] >1:
        res +=1
print(res)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for _ in [0]*n]
    for i in range(m):
        a,b = map(int,ipt().split())
        way[a-1].append((b-1,i))
        way[b-1].append((a-1,i))
    ans = 0
    q = queue.Queue()
    for i in range(m):
        al = [-1 for i in range(n)]
        q.put(0)
        al[0] = 0
        while not q.empty():
            qi = q.get()
            for j,wn in way[qi]:
                if wn == i or al[j] == 0:
                    continue
                else:
                    al[j] = 0
                    q.put(j)
        if -1 in al:
            ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
temp=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  temp[a].append(b)
  temp[b].append(a)
count=0
a=[]
c=True
while c:
  c=False
  for i in range(n):
    if len(temp[i])==1 and i not in a:
      temp[temp[i][0]].remove(i)
      a.append(i)
      count=count+1
      c=True
print(count)

Submission status: Accepted

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

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

changed = True
sumi = []
count = 0
while changed:
    changed = False
    for i in range(len(edges)):
        if len(edges[i]) == 1 and i not in sumi:
            edges[edges[i][0]].remove(i)
            sumi.append(i)
            changed = True
            count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import deque
num_ver, num_edge = map(int,input().split())
edges_ls = [0] * num_edge
for i in range(num_edge):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges_ls[i] = [a,b]

num_bridge = 0
for ind_take_edge in range(num_edge):
    graph_ls = [[] for _ in range(num_ver)]
    # graph_lsを作る
    for ind_edge in range(num_edge):
        if ind_edge != ind_take_edge:
            a,b = edges_ls[ind_edge]
            graph_ls[a].append(b)
            graph_ls[b].append(a)
    
    # 0からdfsしてdone_lsを仕上げていく
    done_ls = [0] * num_ver
    queue = deque()
    queue.append(0)
    while queue:
        now = queue.pop()
        done_ls[now] = 1
        for nex in graph_ls[now]:
            if done_ls[nex] != 1:
                queue.append(nex)
    
    if sum(done_ls) != num_ver:
        num_bridge += 1

print(num_bridge)

Submission status: Accepted

Solution code:

import numpy as np
n,m = list(map(int,input().rstrip().split()))
graph = [[] for _ in range(n)]
route_list = []
for _ in range(m):
    a,b = list(map(int,input().rstrip().split()))
    a -=1
    b -=1
    route_list.append([a,b])
    graph[a].append(b)
    graph[b].append(a)

def dfs(mask, p,graph):
    mask[p] = 1
    if mask.all():
        return True
    nexts = graph[p]
    for n in nexts:
        if mask[n] == 1:
            continue
        else:
            if dfs(mask,n,graph):
                return True
    return False

counter = 0
for r in route_list:
    graph[r[0]].remove(r[1])
    graph[r[1]].remove(r[0])
    mask = np.zeros(len(graph),int)
    if dfs(mask,0,graph) == False:
        counter += 1
    graph[r[0]].append(r[1])
    graph[r[1]].append(r[0])
print(counter)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[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.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    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 0 > x]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = MAP()
ab = [LIST() for _ in range(M)]
ans = 0

for i in range(M):
	tree = UnionFind(N)
	for j in range(M):
		if j != i:
			tree.union(ab[j][0]-1, ab[j][1]-1)
	if tree.group_count() == 2:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

bridge = [list(map(int, input().split())) for i in range(M)]
ans = 0
for i in range(M):
    UF = UnionFind(N)
    for j in range(M):
         if i == j:
              continue
         a, b = bridge[j]
         if not UF.same_check(a, b):
            UF.union(a, b)
    flag = 0
    for k in range(1, N+1):
        if UF.par[k] == k:
            flag += 1
    if flag != 1:
        ans += 1
print(ans)

Submission status: Accepted

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

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, b = [], []
    for _ in range(M):
        aa, bb = map(int, input().split())
        a.append(aa - 1)
        b.append(bb - 1)
    count = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if j == i:
                continue
            uf.union(a[j], b[j])
        if uf.group_count() != 1:
            count += 1
    print(count)

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

n,m = map(int, input().split())
a = [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 (j!=i):
            uf.union(a[j][0]-1,a[j][1]-1)
    if (uf.group_count() !=1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs_traverse(adj, visited, u=0):
  visited[u] = True
  for v in adj[u]:
    if not visited[v]:
      dfs_traverse(adj, visited, v)


def calc_num_of_bridges(edges, adj):
  n = len(adj)
  bridge_cnt = 0
  for a, b in edges:
    adj[a].remove(b)
    adj[b].remove(a)
    # check
    visited = [False] * n
    dfs_traverse(adj, visited)
    if not all(visited):
      bridge_cnt += 1
    # restore
    adj[a].append(b)
    adj[b].append(a)
  return bridge_cnt


n, m = map(int, input().split())
adj = [[] for _ in range(n)]
edges = []
for _ in range(m):
  a, b = map(lambda x: int(x)-1, input().split())
  edges.append((a, b))
  adj[a].append(b)
  adj[b].append(a)

print(calc_num_of_bridges(edges, adj))

Submission status: Accepted

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

road = [[] for _ in range(N)]

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

def dfs(v,w):
  l = [0 for _ in range(N)]
  l[v] = 1
  stack = [v]
  while stack:
    vv = stack.pop()
    for i in road[vv]:
      if i == w and v == vv or i == vv and v == w:
        continue
      else:
        if l[i] == 0:
          l[i] = 1
          stack.append(i)
  return sum(l)

ans = 0
check = [[0 for _ in range(N)] for _ in range(N)]

for n in range(N):
  for m in range(len(road[n])):
    if check[n][road[n][m]] == 0 or check[road[n][m]][n] == 0:
      check[n][road[n][m]] = 1
      check[road[n][m]][n] = 1
      d = dfs(n,road[n][m])
      if d != N:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def dfs(x,tree,al):
    for i in tree[x]:
        if al[i]<0:
            al[i]=0
            dfs(i,tree,al)
    
        
def main():  
    n,m=MI()
    lis=[LI() for i in range(m)]
    #print(lis)
    cou=0
    for i in range(m):
        tree=[[] for i in range(n)]
        for j in range(m):
            if i!=j:
                tree[lis[j][0]-1].append(lis[j][1]-1)
                tree[lis[j][1]-1].append(lis[j][0]-1)
        count=0
        for k in range(n):
            al=[-1]*n
            al[k]=0
            dfs(k,tree,al)
            #print(al)
            if not -1 in al:
                count+=1
        if count!=n:
            cou+=1
    print(cou)    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def dfs(x):
    for i in tree[x]:
        if al[i]<0:
            al[i]=0
            dfs(i)
    
        
    
n,m=MI()
lis=[LI() for i in range(m)]
#print(lis)
cou=0
for i in range(m):
    tree=[[] for i in range(n)]
    for j in range(m):
        if i!=j:
            tree[lis[j][0]-1].append(lis[j][1]-1)
            tree[lis[j][1]-1].append(lis[j][0]-1)
    count=0
    for k in range(n):
        al=[-1]*n
        al[k]=0
        dfs(k)
        #print(al)
        if not -1 in al:
            count+=1
    if count!=n:
        cou+=1
print(cou)

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def dfs(x):
    for i in tree[x]:
        if al[i]<0:
            al[i]=0
            dfs(i)
    
        
    
n,m=MI()
lis=[LI() for i in range(m)]
#print(lis)
cou=0
for i in range(m):
    tree=[[] for i in range(n)]
    for j in range(m):
        if i!=j:
            tree[lis[j][0]-1].append(lis[j][1]-1)
            tree[lis[j][1]-1].append(lis[j][0]-1)
    count=0
    for k in range(n):
        al=[-1]*n
        al[k]=0
        dfs(k)
        #print(al)
        if sum(al)==0:
            count+=1
    if count!=n:
        cou+=1
print(cou)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ls = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

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

def unite(par, rank, x, y):
    rx = find(par, x)
    ry = find(par, y)

    if rx == ry:
        return False
    else:
        if rank[rx] < rank[ry]:
            par[rx] = ry
        else:
            par[ry] = rx
            if rank[rx] == rank[ry]: rank[rx] += 1
        return True

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

c = 0
for i in range(M):
    par = [-1] * N
    rank = [0] * N
    for idx, (a, b) in enumerate(ls):
        if idx == i:
            continue
        unite(par, rank, a, b)
    
    # グループが2つ以上ならばカウント
    if len([i for i, x in enumerate(par) if x < 0]) >= 2:
        c += 1
print(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
data = ILL(M)


ans = 0
for i in range(M):
  graph = [[] for i in range(N)]
  for j in range(M):
    if i != j:
      a,b = data[j]
      graph[a-1].append(b-1)
      graph[b-1].append(a-1)
  d = [0 for i in range(N)]
  q = [0]
  d[0] = 1
  while q:
    u = q.pop()
    for v in graph[u]:
      if d[v] != 1:
        d[v] = 1
        q.append(v)
  if 0 in d:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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=MI()
edge=[]
for i in range(m):
    edge.append(LI())
u=UnionFind(n)
count=0
for i in range(m):
    u=UnionFind(n)
    for j in range(m):
        if i==j:
            continue
        else:
            u.union(edge[j][0]-1,edge[j][1]-1)
    if u.group_count()>1:
        count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    edges = list()
    for _ in range(M):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        edges.append((a, b))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    ans = 0
    for removed_edge in edges:
        a, b = removed_edge
        visited = [0 for _ in range(N)]
        frontier = [0]
        # dfs
        while len(frontier) > 0:
            node = frontier.pop()
            visited[node] = 1
            for next_node in adj_nodes[node]:
                if visited[next_node] == 1:
                    continue
                if (node, next_node) in [(a, b), (b, a)]:
                    continue
                frontier.append(next_node)
        if min(visited) == 0:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
ab = []
for _ in range(m):
    a, b = map(int, input().split())
    ab.append((a-1, b-1))
ans = 0
for i in range(m):
    graph = [[] for _ in range(n)]
    for j in range(m):
        if i==j:
            continue
        a, b = ab[j]
        graph[a].append(b)
        graph[b].append(a)
    q = deque([0])
    seen = [False]*n
    seen[0] = True
    while q:
        node = q.popleft()
        for child in graph[node]:
            if seen[child]:
                continue
            seen[child] = True
            q.append(child)
    if not all(seen):
        ans += 1
print(ans)