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
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

## UnionFind

N, M = mi()
memo = []
rel = [[] for i in range(N)]
#d = dp2(float('inf'), N, N)

for i in range(M):
    s, t = mi()
    s, t = s-1, t-1
    memo.append((s, t))
    rel[s].append(t)
    rel[t].append(s)
    #d[s][t] = d[t][s] = 1
#print(d)

def dfs(v):
    #print(v, used)
    for nv in rel[v]:
    #for nv in range(N):
        if not used[nv]:
        #if d[v][nv] != float('inf') and not used[nv]:
            used[nv] = 1
            dfs(nv)
            if sum(used) == N:
                global flag
                flag = True
                return
            #used[nv] = 0

cnt = M
for x in range(M):
    s, t = memo[x][0], memo[x][1]
    rel[s].remove(t)
    rel[t].remove(s)
    #print(rel)
    #print(s, t)
    #d[s][t] = d[t][s] = float('inf')
    #print(d)
    for i in range(N):
        #print(x, i)
        flag = 0
        used = [0]*N
        used[i] = 1
        dfs(i)
        #print(flag)
        if flag:
            cnt -= 1
            break
    rel[s].append(t)
    rel[t].append(s)
    #d[s][t] = d[t][s] = 1

print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def 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())
ab=[list(map(int,input().split())) for i in range(M)]

ab_copy = [ab[i] for i in range(M)]
ans = 0
for i in range(M):
    ab_copy.pop(i)
    uf = UnionFind(N)
    for j in range(M-1):
        uf.union(ab_copy[j][0]-1,ab_copy[j][1]-1)
    if len(uf.roots())!=1:
        ans += 1
    ab_copy = [ab[i] for i in range(M)]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N, M = mi()
ab = li2(M)
cnt = M

for i in range(M):
    T = UnionFind(N)
    for j in range(M):
        if i != j:
            a, b = ab[j][0]-1, ab[j][1]-1
            if not T.same(a, b):
                T.unite(a, b)
    for k in range(N):
        if T.size(k) != N:
            break
    else:
        cnt -= 1

print(cnt)

Submission status: Accepted

Solution code:
import copy

n, m = map(int, input().split())
G = [[] for i in range(n)] #G(i): 頂点iと隣接する頂点のlist
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
    G[a[i]-1].append(b[i]-1) #入力は 1-indexed とする
    G[b[i]-1].append(a[i]-1) #無向グラフの場合

seen = [0] * n #頂点iが訪問済みの場合 seen[i] = 1

def dfs(g, s, t): #頂点sを始点としたDFS
    seen = [0] * n
    todo = [s]
    while(todo != []):
        v = todo.pop(len(todo)-1) #FILO
        seen[v] = 1
        for i in g[v]:
            if seen[i] == 0:
                todo.append(i)
    return seen[t]

ans = 0
for i in range(m):
    H = copy.deepcopy(G)
    H[a[i]-1].remove(b[i]-1)
    H[b[i]-1].remove(a[i]-1)
    ans += 1-dfs(H, a[i]-1, b[i]-1)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
linked = [[False] * N for _ in range(N)]
edges = []
for i in range(M):
    a, b = map(int, input().split())
    edges.append((a-1, b-1))
    linked[a-1][b-1] = linked[b-1][a-1] = True

def reach(s, g, visited):
    for i in range(N):
        if not linked[s][i]:
            continue
        if i == g:
            return True
        if i not in visited:
            if reach(i, g, visited | {i}):
                return True
    return False

cnt = 0
for i in range(M):
    a, b = edges[i]
    linked[a][b] = linked[b][a] = False
    if not reach(a, b, {a}):
        cnt += 1
    linked[a][b] = linked[b][a] = True
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
graph=[[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
  graph[ab[i][0]-1][ab[i][1]-1]=1
  graph[ab[i][1]-1][ab[i][0]-1]=1
visited=[0 for _ in range(n)]

def dfs(v):
  visited[v]=1
  for v2 in range(n):
    if graph[v][v2]==0:
      continue
    if visited[v2]==1:
      continue
    dfs(v2)

ans=0

for i in range(m):
  graph[ab[i][0]-1][ab[i][1]-1]=0
  graph[ab[i][1]-1][ab[i][0]-1]=0
  for j in range(n):
    visited[j]=0
  dfs(0)
  bridge=0
  for j in range(n):
    if visited[j]==0:
      bridge=1
  if bridge==1:
    ans+=1
  graph[ab[i][0]-1][ab[i][1]-1]=1
  graph[ab[i][1]-1][ab[i][0]-1]=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque

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

    g = tuple(set() for _ in range(N))
    es = []
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)
        es.append((a, b))

    cnt = 0
    for e in es:
        v = 0

        dq = deque()
        dq.append(v)
        used = [False] * N
        used[v] = True

        while dq:
            v = dq.popleft()
            for u in g[v]:
                if used[u]: continue
                if (v, u) == e or (u, v) == e: continue
                used[u] = True
                dq.append(u)

        if all(used): continue
        cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a=[]
b=[]
vector=[[False for i in range(n)] for j in range(n)]

visited = [False]*n
for i in range(m):
  x,y=map(int,input().split())
  a.append(x-1)
  b.append(y-1)
  vector[x-1][y-1]=vector[y-1][x-1]=True
  


def dfs(v):
  visited[v]=True
  for i in range(n):
    if not vector[v][i]:continue
    if visited[i]:continue
    dfs(i)
      
def main():
  ans=0
  for i in range(m):
    vector[a[i]][b[i]]=vector[b[i]][a[i]]=False
  
    for j in range(n):visited[j]=False
   
    dfs(0)
    
    bridge=False
    for j in range(1,n):
      if visited[j]==False:
        bridge=True
    if bridge:
      ans+=1
    vector[a[i]][b[i]]=vector[b[i]][a[i]]=True
    
  print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
INF = float("inf")


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 各要素の親要素の番号を格納するリスト

    def find(self, x):  # 要素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が属するグループと要素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):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# MOD = 10 ** 9 + 7
INF = float("inf")


def dijkstra(s, n, graph):
    dist = [INF] * n
    visited = [False] * n
    dist[s] = 0
    hq = [(0, s)]  # (重み，頂点)
    while hq:
        di, pi = heappop(hq)
        visited[pi] = True
        for dj, pj in graph[pi]:
            if visited[pj]:
                continue
            if dist[pj] > di + dj:
                dist[pj] = di + dj
                heappush(hq, (dist[pj], pj))
    return dist


def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    edge = []
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        graph[a].append((1, b))
        graph[b].append((1, a))
        edge.append((a, b))
    cnt = 0
    for a, b in edge:
        graph[a].remove((1, b))
        graph[b].remove((1, a))
        d = dijkstra(0, N, graph)
        if INF in d:
            cnt += 1
        graph[b].append((1, a))
        graph[a].append((1, b))
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def dfs(start, a, b, visited, n, graph):
    for node in graph[start]:
        if node not in visited:
            if (start, node) == (a, b) or (start, node) == (b, a):
                continue  # (start, node)がなくなっている場合を考えるので，このケースはスルーする
            else:
                visited.append(node)
                dfs(node, a, b, visited, n, graph)
    if len(visited) == n:
        return 0
    else:
        return 1


def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    edge = []
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        graph[a].append(b)
        graph[b].append(a)
        edge.append((a, b))
    cnt = 0
    for a, b in edge:
        cnt += dfs(0, a, b, [], N, graph)
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

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

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

cnt = 0


def dfs(start, a, b, explored, n):
    for node in graph[start]:
        if node not in explored:
            if (start, node) == (a, b) or (start, node) == (b, a):
                continue
            else:
                explored.append(node)
                dfs(node, a, b, explored, n)
    if len(explored) == n:
        return 0
    else:
        return 1
x = 0
for i, j in edge:
    x += dfs(0, i, j, [], n)


print(x)

Submission status: Accepted

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

for i in range(M):
  a,b=map(int, input().split())
  G[a-1].append((i,b-1))
  G[b-1].append((i,a-1))
  
L=[-1]*M
def dfs(start,goal,pre,num):
  if start==goal:
    return False
  done[start]=1
  for i,next_node in G[start]:
    if next_node==pre or i==num or done[next_node]==1:
      continue
    if not dfs(next_node,goal,start,num):
      return False
  return True

for a in range(N):
  for t in G[a]:
    i,b=t
    done=[0]*N
    if L[i]==-1:
      #print(dfs(a,b,-1,i))
      if dfs(a,b,-1,i):
        L[i]=1
      else:
        L[i]=0
print(sum(L))
#print(L)

Submission status: Accepted

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

par=[0]*(N+1)

def find(x):
    if x==par[x]:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

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

def unite(x,y):
    x=find(x)
    y=find(y)

    if x==y:
        return
    
    par[y]=x

ret=0

for i in range(M):
    par=list(range(N+1))

    for j in range(M):
        if i==j:
            continue
        a,b=g[j]

        unite(a,b)
    
    for j in range(1,N+1):
        if not same(1,j):
            ret+=1
            break
    

print(ret)

Submission status: Accepted

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

from collections import deque

def bfs(s, es):
    visited=[0]*n
    visited[s]=1
    q=deque([s])
    while q:
        p=q.pop()
        for r in es[p]:
            if visited[r]==0:
                q.append(r)
                visited[r]=1
    if 0 in visited:
        return False
    else: return True

from copy import deepcopy
ans=0
for e in es0:
    newes=deepcopy(es)
    newes[e[0]].remove(e[1])
    newes[e[1]].remove(e[0])
    if bfs(0,newes):
        continue
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

from collections import deque

def bfs(s, es):
    visited=[0]*n
    visited[s]=1
    q=deque([s])
    while q:
        p=q.popleft()
        for r in es[p]:
            if visited[r]==0:
                q.append(r)
                visited[r]=1
    if 0 in visited:
        return False
    else: return True

from copy import deepcopy
ans=0
for e in es0:
    newes=deepcopy(es)
    newes[e[0]].remove(e[1])
    newes[e[1]].remove(e[0])
    if bfs(0,newes):
        continue
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

def dfs(v, prohibited):
    global visited
    visited[v] = True
    for adj in V[v]:
        if {v, adj} == {lst[prohibited][0], lst[prohibited][1]}: continue
        if visited[adj]: continue
        dfs(adj, prohibited)

ans = 0

# 1本かけた状態で連結しているか否かを判定する
for i in range(M):
    Q = []
    visited = [False] * N
    dfs(0, i)
    if not all(visited): ans += 1 

print(ans)

Submission status: Accepted

Solution code:
def dfs(x):
    if visited[x]:
        return 
    visited[x] = True
    for i in range(n):
        if graph[x][i]:
            dfs(i)

n, m = map(int, input().split())
graph = [[False] * n for _ in range(n)] 
sides = []

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

ans = 0
for side in sides:
    visited = [False] * n
    l, r = side
    graph[l][r] = False
    graph[r][l] = False
    dfs(0)
    if False in visited:
        ans += 1
    graph[l][r] = True
    graph[r][l] = True

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        # union by rank
        self.r = [1]*n
 
    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
 
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]

n,m=map(int,input().split())
e=[]
for i in range(m):
  a,b=map(int,input().split())
  e.append((a-1,b-1))
ans=0
for i in range(m):
  uf=UnionFind(n)
  ok=False
  for j in range(m):
    if i!=j:
      a,b=e[j]
      uf.union(a,b)
  for k in range(n):
    t=uf.count_member(k)
    if t!=n:
      ok=True
      break
  if ok:ans+=1
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
G = [[] for _ in [0]*N]
E = []
for _ in [0]*M:
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    E.append((a, b))


def dfs(v, s, g):
    if v == g:
        return True

    visited[v] = True

    for u in G[v]:
        if visited[u] or v == s and u == g:
            continue
        if dfs(u, s, g):
            return True

    return False


visited = [False]*N

cnt = 0
for a, b in E:
    visited = [False]*N
    visited[a] = True
    if not dfs(a, a, b):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def search_leaf(edge:list):
    """ 葉を取得 """
    for v in range(N):
        if len(edge[v]) == 1: return v
    return -1

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

ans = 0
for _ in range(M):
    V = search_leaf(edge)
    if V == -1: break

    main_land = edge[V][0]
    edge[main_land].remove(V)
    edge[V] = []

    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def bfs(s, n, g):
    que = deque([])
    que.append(s)
    check = [-1] * n
    check[s] = 0
    while que:
        u = que.popleft()
        for v in g[u]:
            if check[v] == -1:
                check[v] = check[u] + 1
                que.append(v)
    if -1 in check:
        return True
    else:
        return False


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    gg = deque([])
    for _ in range(m):
        a, b = [int(i) - 1 for i in input().split()]
        g[a].append(b)
        g[b].append(a)
        gg.append((a, b))
    ans = 0
    for i in range(m):
        a, b = gg.popleft()
        g[a].remove(b)
        g[b].remove(a)
        if bfs(0, n, g):
            ans += 1
        g[a].append(b)
        g[b].append(a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

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

Submission status: Accepted

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

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            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_size(self, x):
        return self.size[self.find(x)]

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = UnionFind(N+1)
    for j in range(M):
        if i == j:
            continue
        u, v = edges[j]
        uf.unite(u, v)
    u, v = edges[i]
    if uf.get_size(u) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
n,m=map(int,input().split())
es=[list(map(int,input().split())) for _ in range(m)]
def check(s,t):
	q=[0]
	vis=[0]*n
	vis[0]=1
	while q:
		c=q.pop()
		for x in con[c]:
			if (c==s and x==t) or (c==t and x==s) or vis[x]:
				continue
			vis[x]=1
			q.append(x)
	return not all(vis)
con=[[] for _ in range(n)]
for s,t in es:
	con[s-1]+=t-1,
	con[t-1]+=s-1,
print(sum(check(s-1,t-1) for s,t in es))

Submission status: Accepted

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

def dfs(start, st, go):
    stack = [start]
    used = set()
    used.add(start)
    while stack:
        here = stack.pop()
        for i in edge[here]:
            if here == st and i == go:
                pass
            elif i == st and here == go:
                pass
            elif i not in used:
                stack.append(i)
                used.add(i)
    return used

ans = 0
for i in range(m):
    tar = bridge[i]
    used = dfs(1, tar[0], tar[1])
    if len(used) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = dict([(i,[]) for i in range(N+1)])
lh = []
for i in range(M):
  a,b = map(int,input().split())
  lh.append([a,b])
  G[a].append(b)
  G[b].append(a)

def bfs(p):
  seen = [False for i in range(N+1)]
  l = [p]
  while len(l)>0:
    v = l.pop(0)
    for i in G[v]:
      if seen[i] == False:
        seen[i] = True
        l.append(i)
      else:
        continue  
  if sum(seen) != N:
    return 1
  else:
    return 0  

cnt = 0
for h in lh:
  a,b = h[0],h[1]
  G[a].remove(b)
  G[b].remove(a)
  cnt += bfs(1)
  G[a].append(b)
  G[b].append(a)
print(cnt)

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)#x,yが同じ集合に属するかどうか


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

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

ans = m
for i in range(m):
  union = UnionFind(n)
  for j in range(m):
    if i == j:
      continue
    union.union(node[j][0], node[j][1])
  key = True
  for j in range(n):
    for k in range(j+1, n):
      if union.same_check(j+1, k+1) == False:
        key = False
  if key:
    ans -= 1
print(ans)

Submission status: Accepted

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

    def dfs(G, v, e):
        seen = [False]*N
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                if (u, next_v) == e or (next_v, u) == e:
                    continue
                seen[next_v] = True
                todo.append(next_v)
        return all(seen)

    ans = 0
    for e in edge_list:
        if dfs(edge, 0, e):
            pass
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n,m = inpl()
g = [[] for _ in range(n)]
r = dict()
cnt = 0
for _ in range(m):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    r[cnt] = (a-1,b-1)
    cnt += 1
res = 0
def chk(g):
    seen = [False] * n
    seen[0] = True
    q = deque([0])
    while q:
        v = q.popleft()
        for nv in g[v]:
            if seen[nv]:
                continue
            seen[nv] = True
            q.append(nv)
    if sum(seen) == n:
        return True
    return False
for i in range(m):
    gg = [[] for _ in range(n)]
    a,b = r[i]
    for j in range(n):
        for k in g[j]:
            if (j,k) == (a,b) or (j,k) == (b,a):
                continue
            gg[j].append(k)
    if not chk(gg):
        res += 1
print(res)

Submission status: Accepted

Solution code:
def dfs(G,v,N):
    seen[v]=True
    for nv in G[v]:
        if(seen[nv]):
            continue
        dfs(G,nv,N)

N,M=map(int,input().split())
xy=[list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
res=0
for i in range(M):
    G=[[] for i in range(N)]
    seen=[False]*N
    for j in range(M):
        if(i==j):
            continue
        G[xy[j][0]].append(xy[j][1])
        G[xy[j][1]].append(xy[j][0])
    cnt=0
    for k in range(N):
        if(not seen[k]):
            dfs(G,k,N)
            cnt+=1
    if(cnt>1):
        res+=1
print(res)