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:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
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()
    ans = 0
    L = tuple(TI() for i in range(M))
    seq = [i for i in range(M)]
    
    for i in seq:
        Union = UnionFind(N)
        for j in filter(lambda x: x != i, seq):
            a, b = L[j]
            Union.union(a-1, b-1)
            
        a, b = L[i]
        if not Union.same(a-1,b-1):
            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 unite(self, x, y):# UF.unite(a-1,b-1)
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):#今回は使っていない
        return -self.parents[self.find(x)]
 
    def same(self, x, y):#UF.same(a-1,b-1) True/False
        return self.find(x) == self.find(y)

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

A=[0]*M;t=0;B=[0]*M

for i in range(M):
  a,b=map(int,input().split())
  A[i]=[a-1,b-1]
for t in range(M):
  UF=UnionFind(N)
  for i in range(M):
    if i!=t:
      UF.unite(A[i][0],A[i][1])
  if UF.same(A[t][0],A[t][1])==False:
    B[t]=1
print(sum(B))

Submission status: Accepted

Solution code:
# coding: utf-8
#union-findを用いた解法
N,M=map(int,input().split())
ans = 0
L = []
def UF(l):
    #親のノードを格納　2の親が4のとき par[2]=4
    par=[0]
    #木の深さを格納　根が2の深さが3の時 rank[2]=3
    rank=[0]
    
    #初期化
    for i in range(1,N+1):
        par.append(i)
        rank.append(0)
    
    #xの根を探す、同時に通過したノードすべてを根に直接つける
    def find(x):
        #xの親がxならば根なのでxを返す
        if par[x]==x:
            return x
        else:
            #違う場合は親の親を捜し自分の親にする
            par[x] = find(par[x])
            #再帰的に行うと根が見つかる
            return par[x]
    
    #xが属する木とyが属する木を併合する
    def unite(x,y):
        #根を探す
        root_x=find(x)
        root_y=find(y)
    
        #根が同じなら元からつながっているので終わり
        if root_x == root_y:
            return
    
        #ランクが大きい木の根の直下にランクが小さい木を結合
        if rank[root_x] < rank[root_y]:
            par[root_x] = root_y
    
        else:
            par[root_y] = root_x
    
        #ランクが等しいときのみランクが増える#なぜ#yにxが結合？
        if rank[root_x]==rank[root_y]:
            rank[root_x]+=1
    
    #xとyが同じ木に存在するかを調べる
    def same(x,y):
        return find(x)==find(y)
    for i in range(M-1):
        a = l[i][0]
        b = l[i][1]
        unite(a, b)
    for i in range(1, N):
        if not same(i, i+1):
            return True

#main
for i in range(M):
    L.append(list(map(int,input().split())))

for i in range(M):
    l = L[0:i] + L[i+1:]
    if UF(l):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N,M=map(int,input().split())
ans = 0
L = []
def UF(l):
    #親のノードを格納　2の親が4のとき par[2]=4
    par=[0]
    #木の深さを格納　根が2の深さが3の時 rank[2]=3
    rank=[0]
    
    #初期化
    for i in range(1,N+1):
        par.append(i)
        rank.append(0)
    
    #xの根を探す、同時に通過したノードすべてを根に直接つける
    def find(x):
        #xの親がxならば根なのでxを返す
        if par[x]==x:
            return x
        else:
            #違う場合は親の親を捜し自分の親にする
            par[x] = find(par[x])
            #再帰的に行うと根が見つかる
            return par[x]
    
    #xが属する木とyが属する木を併合する
    def unite(x,y):
        #根を探す
        root_x=find(x)
        root_y=find(y)
    
        #根が同じなら元からつながっているので終わり
        if root_x == root_y:
            return
    
        #ランクが大きい木の根の直下にランクが小さい木を結合
        if rank[root_x] < rank[root_y]:
            par[root_x] = root_y
    
        else:
            par[root_y] = root_x
    
        #ランクが等しいときのみランクが増える#なぜ#yにxが結合？
        if rank[root_x]==rank[root_y]:
            rank[root_x]+=1
    
    #xとyが同じ木に存在するかを調べる
    def same(x,y):
        return find(x)==find(y)
    for i in range(M-1):
        a = l[i][0]
        b = l[i][1]
        unite(a, b)
    for i in range(1, N):
        if not same(i, i+1):
            return True

#main
for i in range(M):
    L.append(list(map(int,input().split())))

for i in range(M):
    l = L[0:i] + L[i+1:]
    if UF(l):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self,n):
    self.nodes=n
    self.parents=[i for i in range(n)]
    self.sizes=[1]*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 unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x!=y:
      if self.rank[x]<self.rank[y]:
        self.sizes[y]+=self.sizes[x]
        self.parents[x]=y
      else:
        self.sizes[x]+=self.sizes[y]
        self.parents[y]=x
        if self.rank[x]==self.rank[y]:
          self.rank[x]+=1
  def same(self,x,y):
    return self.find(x)==self.find(y)

  def get_parents(self):
    for n in range(self.nodes):
      self.find(n)
    return self.parents

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

ans=0
for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if i==j:
      continue
    uf.unite(*adj[j])  
  if len(set(uf.get_parents()))!=1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] != x:
            stack = [x]
            while True:
                top = stack[-1]
                if self.p[top] == top:
                    break
                else:
                    stack.append(self.p[top])
            for v in stack:
                self.p[v] = top
        return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

N, M = map(int,input().split())
edges = [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: continue
        UF.unite(edges[j][0]-1, edges[j][1]-1)
    
    if UF.components > 1:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(m):
    route = [[] for _ in range(n)]
    for j in range(m):
        if j != i:
            a, b = list_AB[j][0], list_AB[j][1]
            route[a-1].append(b-1)
            route[b-1].append(a-1)

    q = [0]
    l = {0}

    while q:
        x = q.pop(0)
        for p in route[x]:
            if p not in l:
                l.add(p)
                q.append(p)

    if len(list(l)) != n:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.para = [-1] * (n + 1)
    
    def find(self, x):
        if self.para[x] < 0:
            return x
        else:
            self.para[x] = self.find(self.para[x])
            return self.para[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x > y:
            x, y = y, x
        if x == y:
            return
        else:
            self.para[x] += self.para[y]
            self.para[y] = x
    def isSame(self, x, y):
        return self.find(x) == self.find(y)
    
    def count(self,x):
        return -self.para[self.find(x)]
N, M = map(int, input().split())
un_orginal = UnionFind(N)
A = [tuple(map(int, input().split())) for _ in range(M)]
for a,b in A:
    un_orginal.unite(a,b)
ans = 0
for i in range(M):
    un = UnionFind(N)
    for k in range(M):
        if i == k:
            continue
        else:
            un.unite(A[k][0], A[k][1])
    cnt = 0
    for k in range(N+1):
        if un_orginal.count(k) == un.count(k):
            cnt += 1
    if cnt == N+1:
        ans += 1
print(M-ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


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

def dfs(pos):
  if visit[pos] == 1:
    return
  visit[pos] = 1
  
  for i in range(n):
    if graph[pos][i] == 1:
      dfs(i)

count = 0
for hen in range(m):
  graph = [[0]*n for i in range(n)]
  visit = [0]*n

  for i in range(m):
    pos1 = data[i][0] - 1
    pos2 = data[i][1] - 1
    if i != hen:
      graph[pos1][pos2] = 1
      graph[pos2][pos1] = 1
  dfs(0)
  connected = True
  for i in range(n):
    if visit[i] == 0:
      connected = False
  if not connected:
    count += 1
print(count)


# In[ ]:

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
for e in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    a.append(x)
    b.append(y)

def solve(e):
    parent=[i for i in range(N)]
    def find(x,parent):
        y=parent[x]
        while y!=parent[y]:
            y=find(y,parent)
        parent[x]=y
        return y
    def unite(a,b,parent):
        x=find(a,parent)
        y=find(b,parent)
        if x!=y:
            parent[x]=y

    for i in range(M):
        if i==e:
            continue
        unite(a[i],b[i],parent)
    cnt=[0 for _ in range(N)]
    for i in range(N):
        cnt[find(i,parent)]=1
    if cnt.count(1)>1:
        return 1
    else:
        return 0
ans=0
for i in range(M):
    ans+=solve(i)
print(ans)

Submission status: Accepted

Solution code:
n , m = map(int, input().split())
c = [[0]*n for i in range(n)]
for i in range(m):
    a , b = map(int, input().split())
    c[a-1][b-1]=1
    c[b-1][a-1]=1
ans = 0
for k in range(n):
    for i in range(n):
        if sum(c[i])==1:
            ans+=1
            for j in range(n):
                if c[i][j]==1:
                    c[i][j]=0
                    c[j][i]=0
print(ans)

Submission status: Accepted

Solution code:
import queue
n, m = map(int, input().split())
route = [[] for _ in range(n)]
vals = []
for _ in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
    route[b-1].append(a-1)
    vals.append([a-1, b-1])
ans = m
for i in range(m):
    route2 = set()
    q = queue.Queue()
    q.put(0)
    route[vals[i][0]].remove(vals[i][1])
    route[vals[i][1]].remove(vals[i][0])
    while not q.empty():
        a = q.get()
        if not a in route2:
            route2.add(a)
            for j in route[a]:
                q.put(j)
        if len(route2) == n:
            ans -= 1
            break
    route[vals[i][0]].append(vals[i][1])
    route[vals[i][1]].append(vals[i][0])
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())
edges = []
for i in range(M):
    x = list(map(int,input().split()))
    edges.append(x)
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j != i:
            uf.union(edges[j][0]-1,edges[j][1]-1)
        if j == M-1 and uf.group_count() != 1:
            ans += 1
print(ans)

Submission status: Accepted

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

    ans = 0
    for e in edges:
        m[e[0]][e[1]] = 0
        m[e[1]][e[0]] = 0
        global visited
        visited = [0] * N
        dfs(0, m)
        if sum(visited) != N:
            ans += 1
        m[e[0]][e[1]] = 1
        m[e[1]][e[0]] = 1
    print(ans)


def dfs(node, m):
    global visited
    visited[node] = 1
    for i, edge_flag in enumerate(m[node]):
        if edge_flag == 1 and visited[i] != 1:
            dfs(i, m)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
bridges = [None] * M
G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  bridges[i] = (a - 1, b - 1)
  
from collections import deque

ans = 0
for i in range(M):
  q = deque([])
  q.append(0)
  seen = set()
  while q:
    v = q.popleft()
    if v in seen:
      continue
    seen.add(v)
    for child in G[v]:
      if (v, child) == bridges[i] or (child, v) == bridges[i]:
        continue
      q.append(child)
  if len(seen) != N:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))
    
class UnionFind():
    
    # インデックスは0-start
    # 初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
        self.group = n
    
    # private function
    def root(self, x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    # x,yが属するグループの結合
    def union(self, x, y):
        x = self.root(x)
        y = self.root(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
        self.group -= 1
    
    # x,yが同グループか判定
    def same(self, x, y):
        return self.root(x)==self.root(y)

    # xと同じグループの要素数を取得
    def size(self, x):
        return -self.parents[self.root(x)]

######################################################

N,M=mint()
node=[]
for _ in range(M):
    node.append(lint())
ans=0
for i in range(M):
    t=UnionFind(N)
    for j in range(M):
        if j!=i:
            t.union(node[j][0]-1,node[j][1]-1)
    if t.size(0)<N:
        ans+=1
print(ans)

Submission status: Accepted

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

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

  def union(self, x, y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
    
  def size(self, x):
    return -self.parents[self.find(x)]

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

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

  def roots(self):
    return list(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())

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

ans = 0
for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if i == j:
      continue
    uf.union(*adj[j])
  if len(set(uf.roots()))!=1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())

h = [[]*N for _ in range(N)]
AB = []

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

ans = 0

for i in range(M):
    a, b = AB[i]
    h[a].remove(b)
    h[b].remove(a)
    
    fl = [False]*N

    q = deque([0])
    while q:
        t = q.popleft()
        if fl[t]:
            continue
        fl[t] = True
        for tt in h[t]:
            q.append(tt)
    
    if not all(fl):
        ans += 1

    h[a].append(b)
    h[b].append(a)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
s = [[] for i in range(N)]
m = []
for i in range(M):
    a,b = map(int,input().split())
    s[a-1].append(b)
    s[b-1].append(a)
    m.append([a,b])
ans = 0
from collections import deque
import copy
d = deque()
for i in range(M):
    n = [0] * N
    a = m[i][0]
    b = m[i][1]
    c = s[a-1].copy()
    c.remove(b)
    d.append(c)
    n[a-1] = 1
    while len(d) > 0:
        e = d.popleft()
        for j in e:
            if n[j-1] == 0:
                n[j-1] = 1
                d.append(s[j-1])
    if 0 in n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

class node:
    def __init__(self, id):
        self.id = id
        self.root = self

    def findRoot(self):
        if self == self.root:
            return self
        else:
            self.root = self.root.findRoot()
            return self.root

    def resetRoot(self):
        self.root = self

class Tree:
    def __init__(self, num):
        self.nodes = {i:node(i) for i in range(num)}

    def union(self, one, other):
        root1 = one.findRoot()
        root2 = other.findRoot()
        root1.root = root2.root = self.nodes[min(root1.id, root2.id)]

    def resetTree(self):
        for n in self.nodes.values():
            n.resetRoot()

    def makeTree(self, Edge):
        self.edge = Edge
        for x,y in Edge:
            self.union(self.nodes[x-1], self.nodes[y-1])


def main():
    with open(0) as f:
        N, M = map(int, f.readline().split())
        Edge = [tuple(map(int, line.split())) for line in f.readlines()]
    
    tree = Tree(N)
    ans = 0
    for i in range(M):
        edge = [v for  v in Edge if v != Edge[i]]
        tree.makeTree(edge)
        if any(x.findRoot().id != 0 for x in tree.nodes.values()):
            ans += 1
        tree.resetTree()
    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 list(i for i in range(self.n) if self.find(i) == root)

    def roots(self):
        return list(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())

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

ans = 0
for i in range(M): # 取り除く辺の番号
    uf = UnionFind(N)
    for j in range(M): # 辺を追加しない（取り除く）
        if i == j:
            continue
        uf.union(*adj[j])
    if len(set(uf.roots())) != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n,m = i_map()
    ab = [i_list() for i in range(m)]

    def dfs(table):
        visited = [1]
        que = [1]

        while que != []:
            now = que[0]
            del que[0]

            for index, e in enumerate(table[now]):
                if (e==1) & (index not in visited):
                    visited.append(index)
                    que.append(index)
        if len(visited) == n:
            return 0
        else:
            return 1

    ans = 0
    for i in range(m):
        graph = ab.copy()
        del graph[i]
        table = [[0]*(n+1) for i in range(n+1)]
        for a,b in graph:
            table[a][b] = 1
            table[b][a] = 1

        ans += dfs(table)
    print(ans)



if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
routings = [[] for _ in range(N+1)]
for a, b in edges:
  routings[a].append(b)
  routings[b].append(a)

answer = 0
for a, b in edges:
  route = deque([])
  cnt = 0
  checked = [False for i in range(N+1)]
  for r in routings[1]:
    if a == 1 and b == r:
      continue
    else:
      route.append(r)
      cnt += 1
      checked[r] = True
  while len(route) > 0:
    current = route.popleft()
    for next in routings[current]:
      if not checked[next] and (min(current, next) != a or max(current, next) != b):
        route.append(next)
        cnt += 1
        checked[next] = True
  if cnt < N:
    answer += 1
print(answer)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,N):
        self.par=[-1]*N
    
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.par[x] > self.par[y]:
            x,y = y,x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True
    
    def root(self,x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    
    def size(self,x):
        return -self.par[self.root(x)]

N,M = map(int,input().split())
Edge = []
for _ in range(M):
    u,v = map(int,input().split())
    Edge.append((u-1,v-1))

ans = 0

for e in Edge:
    uf = UnionFind(N)
    for _e in Edge:
        if e == _e:
            continue
        uf.unite(_e[0],_e[1])
    if uf.size(0) != N:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def check(G, n):
    for a in range(n):
        for b in range(a+1, n):
            if G._root(a) != G._root(b):
                return True
    return False


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    ab = [list(map(int, x.split())) for x in sys.stdin.buffer.readlines()]
    ans = 0
    for i in ab:
        G = UnionFind(n)
        for j in ab:
            if i != j:
                G.union(j[0]-1, j[1]-1)
        if check(G, n):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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(br(n, m, g))


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