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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

def dfs(s, t, conn, visited):
    #print(s, t, visited)
    #print(s, t, conn)
    if s == t:
        return True
    visited[s] = True
    for n in conn[s]:
        if not visited[n] and dfs(n, t, conn, visited):
            return True
    return False


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    #conn = [[False] * N for _ in range(N)]
    ret = 0
    for i in range(M):
        conn = [[] for _ in range(N)]
        for j in range(M):
            if i == j:
                continue
            conn[a[j] - 1].append(b[j] - 1)
            conn[b[j] - 1].append(a[j] - 1)
        visited = [False] * N
        if not dfs(a[i] - 1, b[i] - 1, conn, visited):
            #print(a[i] - 1, b[i] - 1)
            #print()
            ret += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = []
for i in range(0, M):
	edges.append(list(map(int, input().split())))
cnt = 0
for i in range(0, M):
	grp = []
	for j in range(0, N):
		lst = []
		for k in range(0, N):
			lst.append(False)
		grp.append(lst)
	for j in range(0, M):
		if i != j:
			grp[edges[j][0]-1][edges[j][1]-1] = True
			grp[edges[j][1]-1][edges[j][0]-1] = True
	memo = []
	for j in range(0, N):
		memo.append(True)
	queue = [0]
	while queue != []:
		now = queue.pop(0)
		memo[now] = False
		if True not in memo:
			break
		for j in range(0, N):
			if grp[now][j] and memo[j]:
				queue.append(j)
	if True in memo: cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import copy

n,m=list(map(int,input().split()))
way=[[] for _ in range(n)]
edge=[]
for i in range(m):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    way[a].append(b)
    way[b].append(a)
    edge.append((a,b))
checked=[False]*n

new_way=[]

def searchWay(current,to):
    flg=False
    checked[current]=True
    for i in new_way[current]:
        if i == to:
            return True
        else:
            if not checked[i]:
                if searchWay(i,to):
                    flg=True
                    break
    return flg

ans=0
for i in edge:
    checked=[False]*n
    new_way=copy.deepcopy(way)
    new_way[i[0]].remove(i[1])
    new_way[i[1]].remove(i[0])
    if not searchWay(i[0],i[1]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:


LIM = 50

graph =[[False  for _  in range(LIM)] for _ in range(LIM)]
visited = [False  for _  in range(LIM)]
bridges = []


def search(num):
    visited[num] = True
    for i, temp in enumerate(graph[num]):
        if not temp:  # つながってなかったら
            continue
        if visited[i]:  # 訪問済みならx
            continue
        search(i)


def do():
    ans = 0
    N ,M = list(map(int,input().split(" ")))
    for _ in range(M):
        a,b = list(map(int,input().split(" ")))
        a -= 1
        b -= 1

        bridges.append([a,b])
        graph[a][b] =  graph[b][a] = True
    for bridge in bridges: #M番目を落とす
        graph[bridge[0]][bridge[1]] = graph[bridge[1]][bridge[0]] = False
        for j in range(LIM):
            visited[j] = False
        search(0) #0から始めて良い∵連結グラフなので
        flag = False

        for i in range(N):
            if visited[i] == False:
                flag = True
        if flag:
            ans +=1
        graph[bridge[0]][bridge[1]] = graph[bridge[1]][bridge[0]] = True
    print(ans)





if __name__ == "__main__":
    do()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
graph=list([0]*N for _ in range(N))
ans=0
for a,b in ab:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

def dfs(s):
    visited[s]=1
    for i in range(N):
        if graph[s][i] == 0 or visited[i] == 1:
            continue
        dfs(i)

for a,b in ab:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited=[0]*N
    dfs(0)
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
    if sum(visited)<N:
        ans+=1


print(ans)

Submission status: Accepted

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

graph = [[0] * N for _ in range(N)]
for a, b in edges:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1


def dfs(v):
    visited[v] = 1
    for v2 in range(N):
        if graph[v][v2]==0 or visited[v2]==1:#vとv2が隣接していない or すでに訪れている場合
            continue
        dfs(v2)#隣接していて、まだ訪れていない場合


ans = 0
for a, b in edges:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited = [0] * N

    dfs(0)

    bridge = 0
    if sum(visited) < N :
        bridge = 1
        ans+=1
        
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

print(ans)

Submission status: Accepted

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

graph = [[0] * N for _ in range(N)]
for a, b in edges:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1


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 a, b in edges:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited = [0] * N

    dfs(0)
    # print(visited)

    bridge = 0
    for i in range(N):
        if visited[i] == 0:
            bridge = 1
    if bridge==1:
        ans += 1

    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

print(ans)

Submission status: Accepted

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

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

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)

ans = 0

for i in range(M):
    u = UnionFind(N)
    for j in range(M):
        if i != j:
            u.unite(L[j][0] - 1, L[j][1] - 1)

    for j in range(N - 1):
        if u.same(j, j + 1) == False:
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=[[] for i in range(N)]
AB=[]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    ab[a].append(b)
    ab[b].append(a)
    AB.append([a,b])
ans=0
for i in range(M):
    x,y=AB[i]
    ab[x].remove(y)
    ab[y].remove(x)
    stack=[i for i in ab[0]]
    reached=[0]*N
    reached[0]=1
    while(stack):
        b=stack.pop()
        if reached[b]==1:
            continue
        for k in ab[b]:
            stack.append(k)
        reached[b]=1
    ab[x].append(y)
    ab[y].append(x)
    if reached!=[1]*N:
        ans+=1
print(ans)

Submission status: Accepted

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

graph = [[False] * N for _ in range(N)]
for a, b in edges:
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True

def dfs(v):
    visited[v] = True
    for v2 in range(N):
        if not graph[v][v2]:
            continue
        if visited[v2]:
            continue
        dfs(v2)
    
ans = 0
for a, b in edges:
    graph[a - 1][b - 1] = False
    graph[b - 1][a - 1] = False
    visited = [False] * N
    
    dfs(0)
    # print(visited)
    
    bridge = False
    for i in range(N):
        if visited[i] == False:
            bridge = True
    if bridge:
        ans += 1
        
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True
    
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a,b,ans = [[] for _ in range(n)],[],0
def solve(v,aa,bb):
    visited[v] = True
    for n in a[v]:
        if not visited[n] and set([v,n]) != set([aa,bb]):
            solve(n,aa,bb)

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

for i in range(m):
    visited = [True]+[False]*(n-1)
    x,y = b[i]
    solve(0,x,y)
    if visited != [True]*n:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lis = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)
counter = 0
flag = True
while flag:
    flag = False
    for index in range(1, N+1):
        if len(lis[index]) == 1:
            lis[lis[index][0]].remove(index)
            lis[index].pop(0)
            counter += 1
            flag = True
print(counter)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

N,M=[int(val) for val in input().split()]
a=deque()
b=deque()

for i in range(M):
  x,y = (int(val) for val in input().split())
  a.append(x)
  b.append(y)

cnt=0
for j in range(M):
    
    val_a=a.popleft()
    val_b=b.popleft()

    stack=deque([1])
    visited=deque()

    while len(stack) > 0:
        val=stack.pop()
        if visited.count(val)==0:
            visited.append(val)
            for i in range(len(a)):
                if a[i]==val:
                    if b[i] != visited:
                        stack.append(b[i])
            for i in range(len(b)):
                if b[i]==val:
                    if a[i] != visited:
                        stack.append(a[i]) 
                        
    if len(visited) < N:
        cnt+=1
    
    a.append(val_a)
    b.append(val_b)

print(cnt)

Submission status: Accepted

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


def dfs(v):
    global visited
    visited[v] = 1
    for u in range(1, n + 1):
        global graph
        if u in graph[v] and visited[u] == 0:
            dfs(u)


def main():
    ans = m
    for i in range(m):
        global graph
        graph = [[] for _ in range(n + 1)]
        for j, e in enumerate(edge):
            if i == j:
                continue
            v, u = e
            graph[v].append(u)
            graph[u].append(v)
        global visited
        visited = [0] * (n + 1)
        dfs(1)
        if all(visited[1:]):
            ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(L,res):
    for i in range(1,N+1):
        #print(i,L[i])
        if len(L[i]) == 1:
            L[L[i][0]].remove(i)
            L[i] = []
            res = f(L,res+1)
    return res


N,M = map(int,input().split())
L = [[] for _ in range(N+1)]

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

Submission status: Accepted

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


parent = [i for i in range(N)]
rank = [0] * N


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


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

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1

num = 0
for a, b in S:
    parent = [i for i in range(N)]
    rank = [0] * N
    for c, d in S:
        if c == a and b == d:
            continue
        else:
            unite(c, d)

    flag = False
    for i in range(N):
        if flag:
            break
        for j in range(N):
            if not same(i, j):
                flag = True
                break

    if flag:
        num += 1


print(num)

Submission status: Accepted

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

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

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

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

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

cnt = 0
for i in range(M):
    un = UnionFind(N+1)
    for ind,x in enumerate(ab):
        if(ind!=i):
            un.unite(x[0],x[1])

    if(un.find(ab[i][0])!=un.find(ab[i][1])):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
import sys


def check(route,N):
  dct = {i:[] for i in range(1,N+1)}
  for a,b in route:
    dct[a].append(b)
    dct[b].append(a)

  nxt = [1]
  visited = set()
  while len(nxt)>0 and len(visited)<N:
    p = nxt.pop(0)
    visited.add(p)
    for q in dct[p]:
      if q not in visited:
        nxt.append(q)      

  if len(visited)<N:
    return 1
  else:
    return 0


def main():
  ## input
  N,M = map(int, input().split())
  route = []
  for _ in range(M):
    route.append(list(map(int, input().split())))

  ## solve
  ans = 0
  for i in range(M):
    ans += check(route[0:i]+route[i+1:], N)    
  return ans

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

Submission status: Accepted

Solution code:
import collections
v,e=map(int,input().split())
g=[list(map(int,input().split())) for _ in range(e)]
ans=0
for i in range(e):
  tmp=g[:i]+g[i+1:]
  ga=[[] for _ in range(v+1)]
  for j in range(e-1):
    s,t=tmp[j][0],tmp[j][1]
    ga[s].append(t)
    ga[t].append(s)
  visited=[0]*(v+1)
  queue=collections.deque([1])
  visited[1]=1
  while 1:
    if len(queue)==0:
      break
    tv=queue.popleft()
    for i in ga[tv]:
      if visited[i]==0:
        queue.append(i)
        visited[i]=1
  if visited.count(1)!=v:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, M = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for _ in range(M)]

count = 0
for a, b in AB:
    uf = UnionFind(N + 1)
    for c, d in AB:
        if (a, b) == (c, d):
            continue
        uf.union(c, d)
    if uf.size(1) != N:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import deque as deque
def IsBridgeBFS(m):#m辺目をぶっこ抜いたDFS
    newlines=[[] for oiejfo in range(N)]
    for k,line in enumerate(lines):
        x,y=line
        if k==m:continue
        newlines[x].append(y)
        newlines[y].append(x)
    stack=deque()
    went=[False]*N
    stack.append(0)
    went[0]=True
    while stack:
        cur=stack.pop()
        for togo in newlines[cur]:
            if not went[togo]:
                went[togo]=True
                stack.append(togo)
    return(not all(went))#bridge:True

N,M=[int(k) for k in input().split()]#N頂点N辺
lines=[[int(j)-1 for j in input().split()]for i in range(M)]

print(sum([IsBridgeBFS(k) for k in range(M)]))

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.find(self.par[x])
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    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

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

ans = 0
for i in range(M):
    path = UnionFind(N)
    for j in range(M):
        if j != i:
            path.union(a[j], b[j])
    flag = True
    for j in range(N):
        for k in range(j, N):
            if not path.same_check(j, k):
                flag = False
    if not flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""解説
Union-Find

i番目の辺(ai, bi)を除く全ての辺を使ってUnion-Find木を作る。

その後、ai と bi がつながっているかを判定する。つながっていないならば、ai,biの辺は橋である。

この操作をすべてのiにおいて全探索する。

【計算量】
たぶんO(M(N+M))

Union-Findによるあるノード(a, b)が同じグループかどうか（今回では、同じグループ＝繋がっている）
の判定は高速でできる。

"""
class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self.parent = [n for n in range(0, N)]
        # グループの深さ
        self.depth = [1] * N

    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) # 縮約
        return self.parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self.depth[gx] < self.depth[gy]:
            self.parent[gx] = gy
        else:
            self.parent[gy] = gx
            if self.depth[gx] == self.depth[gy]: self.depth[gx] += 1

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)


def solve():
    N, M = list(map(int, input().split()))
    edges = []

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

    # 各辺について、その辺が存在しない時、aとbが連結になるかをUnion-Findで判定する
    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, edge in enumerate(edges):
            if i == j: continue
            
            a, b = edge
            uf.unite(a, b)
        
        # i番目の辺を除くすべての辺をつないだあとで、i番目の辺(a, b)がつながるかを判定する
        # つながらないならば、そのi番目の辺は橋である
        a, b = edges[i]
        if not uf.is_same_group(a, b): ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""解説
Union-Find

i番目の辺(ai, bi)を除く全ての辺を使ってUnion-Find木を作る。

その後、ai と bi がつながっているかを判定する。つながっていないならば、ai,biの辺は橋である。

この操作をすべてのiにおいて全探索する。

【計算量】
たぶんO(NM)

Union-Findによるあるノード(a, b)が同じグループかどうか（今回では、同じグループ＝繋がっている）
の判定は高速でできる。

"""
class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self.parent = [n for n in range(0, N)]
        # グループの深さ
        self.depth = [1] * N

    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) # 縮約
        return self.parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self.depth[gx] < self.depth[gy]:
            self.parent[gx] = gy
        else:
            self.parent[gy] = gx
            if self.depth[gx] == self.depth[gy]: self.depth[gx] += 1

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)


def solve():
    N, M = list(map(int, input().split()))
    edges = []

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

    # 各辺について、その辺が存在しない時、aとbが連結になるかをUnion-Findで判定する
    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, edge in enumerate(edges):
            if i == j: continue
            
            a, b = edge
            uf.unite(a, b)
        
        # i番目の辺を除くすべての辺をつないだあとで、i番目の辺(a, b)がつながるかを判定する
        # つながらないならば、そのi番目の辺は橋である
        a, b = edges[i]
        if not uf.is_same_group(a, b): ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

ab = {}
for a, b in AB:
	if not a in ab:
		ab[a] = [b]
	else:
		ab[a] += [b]
	if not b in ab:
		ab[b] = [a]
	else:
		ab[b] += [a]

def check():
	for i in ab:
		if 1 == len(ab[i]):
			return True
	else:
		return False

c = 0
while check():
	for p in ab:
		if 1 == len(ab[p]):
			c += 1
			ab[ab[p][0]].remove(p)
			del ab[p][0]

print(c)

Submission status: Accepted

Solution code:
def check(i,adj):
    visited = [False]*N
    visited[i] = True
    q = [i]
    while q != []:
        v = q.pop(0)
        for w in adj[v]:
            if not visited[w]:
                visited[w] = True
                q.append(w)
    return all(visited)
N,M = map(int,input().split())
adj = [[] for i in range(N)]
edges = []
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges.append((a,b))
    adj[a].append(b)
    adj[b].append(a)
ans = 0
for a,b in edges:
    tmp = [adj[i].copy() for i in range(N)]
    tmp[a].remove(b)
    tmp[b].remove(a)
    if not check(0,tmp):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
	def __init__(self, n):
		self.graph = [i for i in range(n)]

	def find(self, n):
		if self.graph[n] == n:
			return n
		self.graph[n] = self.find(self.graph[n])
		return self.graph[n]

	def union(self, n, m):
		self.graph[self.find(self.graph[m])] = self.find(self.graph[n])

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

ans=0

for j in range(M):
	uf = UnionFind(N+1)
	for i in range(M):
		if i == j:
			continue
		uf.union(*bridge[i])
	if len(set([uf.find(n) for n in range(1, N+1)])) > 1:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
inf = 10**9
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
bridge_list = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    bridge_list.append([a, b])
ans = 0
for a, b in bridge_list:
    graph_copy = copy.deepcopy(graph)
    graph_copy[b].remove(a)
    graph_copy[a].remove(b)
    distance_list = [inf] * n
    distance_list[0] = 0
    visited = set([])
    point = set([0])
    while len(point - visited) > 0:
        vvv = [[vv, i] for i, vv in enumerate(distance_list) if i in (point - visited)]
        u = min(vvv)[1]
        for v in graph_copy[u]:
            if distance_list[u] + 1 < distance_list[v]:
                distance_list[v] = distance_list[u] + 1
                point.add(v)
        visited.add(u)
    if distance_list.count(inf) > 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

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

cnt = 0

from collections import deque

for i in a:
    b = a[:]
    start = i[0]
    goal = i[1]
    b.remove(i)
    q = deque()
    q.append(start)

    searched = {start}
    while q:
        current = q.popleft()
        if current == goal:
            break
        for j in b:
            if current == j[0] and j[1] not in searched:
                q.append(j[1])
                searched.add(j[1])
            elif current == j[1] and j[0] not in searched:
                q.append(j[0])
                searched.add(j[0])
    else:
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
E = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)
    E.append((a, b))
used = [-1] * N


def dfs(u, a, b):
    used[u] = 1
    for w in G[u]:
        if (u == a and w == b) or (u == b and w == a):
            continue
        if (w, u) in s:
            continue
        s.add((w, u))
        dfs(w, a, b)


num = 0
for a, b in E:
    used = [-1] * N
    s = set()
    dfs(0, a, b)
    if sum(used) != N:
        num += 1

print(num)

Submission status: Accepted

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

ans = 0
for i in range(M):
    ab2 = ab[:i] + ab[i+1:]
    connect = [[] for _ in range(N+1)]
    for a,b in ab2:
        connect[a].append(b)
        connect[b].append(a)
    V = [-1] * (N+1)
    V[0] = 0
    V[1] = 0
    q = [1]
    for j in q:
        for k in connect[j]:
            if V[k] == -1:
                V[k] = V[j] + 1
                q.append(k)
    
    for v in V[1:]:
        if v == -1:
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
link = [[0] * (N+1) for i in range(N+1)]
links = []
count = 0

def dfs(pos):
    if reached[pos]:
        return
    reached[pos] = 1
    for next in range(N+1):
        if link[pos][next]:
            dfs(next)

for i in range(M):
    a, b = map(int, input().split())
    links.append([a, b])
    link[a][b] = 1
    link[b][a] = 1

for a, b in links:
    link[a][b] = 0
    link[b][a] = 0
    reached = [0] * (N+1)
    dfs(1)
    if all(reached[1:]) == False:
        count += 1
    link[a][b] = 1
    link[b][a] = 1

print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())

x=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    if b not in x[a-1]:
        x[a-1].append(b)
        if a not in x[b-1]:
            x[b-1].append(a)

ans=0

while True:
    idx,flg=0,0
    for i in x:
        if len(i)==1:
            flg=1
            x[i[0]-1].remove(idx+1)
            x[idx]=[]
            ans+=1
        idx+=1
    if flg==0:
        break
print(ans)

Submission status: Accepted

Solution code:
n,m = [int(it) for it in input().split()]
li=[]
lim=[]
dcli=[ [] for i in range(n)]
for i in range(m):
  a,b = [int(it)-1 for it in input().split()]
  li.append( (a,b) )
  li.append( (b,a) )
  lim.append((a,b))
  dcli[a].append(b)
  dcli[b].append(a)
[ dcli[i].sort() for i in range(n)]
import numpy as np
import copy 
#print (n,m,li)
#print (dcli)
mi=np.ones([n],dtype=np.int)-1
ma=np.ones([n],dtype=np.int)-1
now = 0
stc=[0]
al=[0]
for i in range(10000):
  if len(dcli[now])>0:
    _now = dcli[now][0]
    if (len(stc)>1):
      if stc[-2] != _now:
        #print (_now,stc) 
        tmp = copy.copy(stc)
        tmp.append(_now)
        #print ("*",tmp)
        ind = 0
        for k in range(len(tmp)):
          if (tmp[k]==_now):
            ind = k
            break
        cut = tmp[ind:]
        if (len(cut)>1):
          for i in range(len(cut)-1):
            #print ("cut",cut[i],cut[i+1])
            if (min(cut[i],cut[i+1]),max(cut[i],cut[i+1])) in lim:
              lim.remove((min(cut[i],cut[i+1]),max(cut[i],cut[i+1])))
    else:
      pass
      #print (_now,stc)
    if _now in al:
      dcli[now] = dcli[now][1:]
      #print ("<"+str(_now)+">",end="")
      
      continue
    #print (_now,end=",") 
    al.append(_now)
    stc.append(_now)
    #mi[now]=min(mi[now],_now)
    #mi[now]=min(mi[now],_now)
    now = _now
  else:
    stc = stc[:-1]
    if (len(stc)==0):
      break
    now = stc[-1]
    #print ("R",end="")
#print ( lim , "happy" ) 
print (len(lim))

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
a, b = [], []
for _ in range(m):
  a_, b_ = [int(i) for i in input().split()]
  a.append(a_)
  b.append(b_)
  
nodes = list(set(a)|set(b))

def dfs(node, visited, neighbors):
    visited[node] = 1
    candidates = [
        k for k, v in visited.items()
        if v==0 and k in neighbors[node]]
    
    for new_node in candidates:
        visited = dfs(new_node, visited, neighbors)
    
    return visited
  
bridges = 0
for idx in range(len(a)):
    
    a_ = [x for i, x in enumerate(a) if i!=idx]
    b_ = [x for i, x in enumerate(b) if i!=idx]
    
    neighbors = {x:set() for x in nodes}
    for k, (i, j) in enumerate(zip(a_, b_)):        
        neighbors[i].add(j)
        neighbors[j].add(i)
    
    visited = {x:0 for x in nodes}
    visited = dfs(a_[0], visited, neighbors)
    
    not_visited = sum([v==0 for k, v in visited.items()])
    if not_visited:
        bridges += 1
        
print(bridges)