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:
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 r'\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
a=[None]*m
b=a[:]
ans=0
for i in range(m):
  a[i],b[i]=map(lambda x:x-1,map(int,input().split()))
for i in range(m):
  u=UnionFind(n)
  for j in range(m):
    if j!=i:
      u.union(a[j],b[j])
  if u.size(0)!=n:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
node = [list(map(int, input().split())) for _ in range(m)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = node[i]
    graph[a].append(b)
    graph[b].append(a)

ans = 0
for i in range(m):
    x, y = node[i]
    q = deque([1])
    visited = [0] * (n+1)
    while q:
        now = q.popleft()
        visited[now] = 1
        for g in graph[now]:
            if now == x and g == y:
                continue
            if now == y and g == x:
                continue
            if visited[g]:
                continue
            else:
                q.append(g)
    if sum(visited) == n:
        pass
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

N,M=map(int,input().split())
a=[0]*M
b=[0]*M
bridge=0
for i in range(0,M):
    a[i],b[i]=map(int,input().split())
for i in range(0,M):
    V={1}
    while True:
        X=copy.copy(V)
        v=len(V)
        for j in X:
            for k in range(0,M):
                if a[k]==j and k!=i:
                    V.add(b[k])
                elif b[k]==j and k!=i:
                    V.add(a[k])
        test=len(V)
        if test==N:
            break
        elif test==v:
            bridge+=1
            break
print(bridge)

Submission status: Accepted

Solution code:
stack = []

def dfs(visited):
    while 0 < len(stack):
        v = stack.pop()
        for i, u in enumerate(edges[v]):
            if u is True:
                if visited[i]:
                    continue
                visited[i] = True
                stack.append(i)
                dfs(visited)


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

ans = 0
for a, b in zip(A, B):
    edges[a][b] = False
    edges[b][a] = False
    visited = [False] * N
    cnt = 0
    for v in range(N):
        if visited[v]:
            continue
        cnt += 1
        visited[v] = True
        stack.append(v)
        dfs(visited)
    if 1 < cnt:
        ans += 1
    edges[a][b] = True
    edges[b][a] = True
print(ans)

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(list)
B = []
for _ in range(m):
    a1, a2 = list(map(int, input().split()))
    B.append([a1, a2])
    d[a1].append(a2)
    d[a2].append(a1)
    
def dfs(a, conn):
    memo[a] = 1
    for c in conn:
        if memo[c] == 0:
            dfs(c, d[c])
            
cnt = 0
for b in B:
    a1, a2 = b
    memo = [0]*(n+1)
    conn = set(d[a1]) - set([a2])
    dfs(a1, conn)
    if memo.count(1) != n:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
d=[[] for i in range(N)]
for i in range(M):
    b, c = map(int, input().split())
    d[b-1].append(c-1)
    d[c-1].append(b-1)
a=0
while True:
    count = 0
    for i in range(N):
        if len(d[i]) == 1:
            d[d[i][0]].remove(i)
            d[i]=[]
            count += 1
    if count == 0:
        break
    a+=count
print(a)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
a=0
while 1:
    x=0
    for i in range(n):
        if len(l[i])==1:
            l[l[i][0]].remove(i)
            l[i]=[]
            x+=1
    if x==0:break
    a+=x
print(a)

Submission status: Accepted

Solution code:
def saiki(bang, abbali, tf):

    ans = 0
    if all(tf) == True:
        return 1
    stack = []
    for i in range(len(abbali)):
        if abbali[i][0] == bang and tf[abbali[i][1]-1] == False:
            stack.append(abbali[i][1])

    for i in range(len(stack)):
        tf[stack[i]-1] = True
        ans += saiki(stack[i], abbali, tf)
    return ans

def bridge(n , m , abl):

    ans = 0
    for i in range(m):
        abbali = []
        count = 0
        tf = [False]*n
        for q in range(m):
            if i != q:
                abbali.append(list((abl[q])))
                abbali.append(list(reversed(abl[q])))
        count = saiki(1, abbali, tf)
        ans += count if count < 1 else 1

    return m - ans

def main():
    n , m = map(int , input().split())
    abl = [list(map(int , input().split())) for i in range(m)]
    print(bridge(n , m , abl))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
paths=[]
a=[]
b=[]
for i in range(n):
    paths.append([0]*n)
for i in range(m):
    a_i,b_i=map(int,input().split())
    paths[a_i-1][b_i-1]=1
    paths[b_i-1][a_i-1]=1
    a.append(a_i)
    b.append(b_i)
visited=[0]*n

def dfs(now):
    visited[now]=1
    for i in range(n):
        if paths[now][i]==1 and visited[i]==0:
            dfs(i)
    return

ans=0
for i in range(m):
    visited=[0]*n
    a_i=a[i]
    b_i=b[i]
    paths[a_i-1][b_i-1]=0
    paths[b_i-1][a_i-1]=0
    dfs(a_i)
    if sum(visited)!=n:
        ans+=1
    paths[a_i-1][b_i-1]=1
    paths[b_i-1][a_i-1]=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

if __name__ == "__main__":
    n, m = map(int, input().split())
    edge = list()
    for i in range(m):
        edge.append(list(map(int, input().split())))

    ans = 0

    for i in range(m):
        distance = [-1] * n
        que = deque([0])
        graph = dict()
        for j in range(n):
            graph[j] = []

        distance[0] = 0  # 初期条件(スタート地点)

        for j in range(m):
            if i != j:
                graph[edge[j][0]-1].append(edge[j][1]-1)
                graph[edge[j][1]-1].append(edge[j][0]-1)

        # 幅優先探索
        while len(que) != 0:
            v = que.popleft()
            for g in graph[v]:
                if distance[g] != -1:
                    continue
                distance[g] = distance[v] + 1
                que.append(g)

        for d in distance:
            if d == -1:
                ans += 1
                break

    print(str(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？


"""
グラフ入力例
n,m=mii()
g = [[] for _ in range(n)]
seen = [0]*n
for i in range(m):
    x,y=mii()
    g[x-1].append(y-1)
    g[y-1].append(x-1)
    
"""
#g:グラフ v:スタート地点
def dfs(g, v):
	seen[v] += 1
    #スタート地点
	#print('v :', v)
	
	for nv in g[v]:
		if seen[nv]: continue
        #次の場所
		#print('v nv :', v, nv, 'Recursion')
		dfs(g, nv)

n,m=mii()
arr = []
for i in range(m):
    x,y=mii()
    arr.append([x,y])

ans = 0
for i in range(m):
	g = [[] for _ in range(n)]
	for j, m in enumerate(arr):
		if i != j:
			a, b = m
			g[a-1].append(b-1)
			g[b-1].append(a-1)
		
	seen = [0]*n
	dfs(g, 1)
	#print(i, j, seen)
	
	if sum(seen) != n: ans += 1

print(ans)

Submission status: Accepted

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

graph = [[False] * N for _ in range(N)]
queries = []


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


def dfs(node, visited):
    global graph
    for i, next in enumerate(graph[node]):
        if next and i not in visited:
            visited.append(i)
            dfs(i, visited)
    return visited


cnt = 0
for q in queries:
    graph[q[0]][q[1]] = False
    graph[q[1]][q[0]] = False
    visited = dfs(0, [])
    if len(visited) != N:
        cnt += 1
    graph[q[0]][q[1]] = True
    graph[q[1]][q[0]] = True

print(cnt)

Submission status: Accepted

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

def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]

def is_same(a,b):
    return root(a) == root(b)

def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;
 
ans = 0
for i in range(M):
    parent = [k for k in range(N)]
    for j,e in enumerate(es):
        if j == i: continue
        a,b = e
        unite(a,b)
    a,b = es[i]
    if not is_same(a,b):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, m = map(int, input().split())
    edge = list()
    for i in range(m):
        edge.append(list(map(int, input().split())))

    ans = 0

    def dfs(v):
        visted[v] = True
        for i in range(n):
            if graph[v][i] is False:
                continue
            if visted[i] is True:
                continue
            dfs(i)

    for i in range(m):
        visted = [False] * n
        graph = [[False] * n for _ in range(n)]

        for j in range(m):
            if i != j:
                graph[edge[j][0]-1][edge[j][1]-1] = True
                graph[edge[j][1]-1][edge[j][0]-1] = True
        dfs(0)
        if visted != [True] * n:
            ans += 1

    print(str(ans))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m = map(int,readline().split())
lst1 = [list(map(int,readline().split())) for i in range(m)]

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点



ans = 0 #橋
for i in range(m):
    par = [-1]*n
    for j in range(m):
        if i == j:
            continue
        else:
            unite(lst1[j][0]-1,lst1[j][1]-1)
    if group_count() != 1:
        ans += 1
print(ans)

Submission status: Accepted

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

ab = []
v = [[] for _ in range(n+1)]
for _ in range(m):
  a, b = map(int, input().split())
  ab.append([a, b])
  v[a].append(b)
  v[b].append(a)

ans = 0
for a, b in ab:
  visited = set()
  q = collections.deque()
  q.append(1)
  visited.add(1)
  while q:
    c = q.pop()
    for i in v[c]:
      if i in visited:
        continue
      if (a == i and b == c) or (a == c and b == i):
        continue
      q.append(i)
      visited.add(i)
  if len(visited) != n:
    ans += 1
    
print(ans)

Submission status: Accepted

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

G = [[] for _ in range(N+1)]
for i in range(M):
    c,d = map(int,input().split())
    G[c].append(d)
    G[d].append(c)


#i番目の辺を取り除いたときに非連結となる
#i番目の辺を取り除いたときにグラフが連結かどうかを調べる
ans = 0
for i in range(M):
    for j in range(1,N+1):
        #頂点jに接続している辺の数が１のとき
        if len(G[j]) == 1:
            tmp = G[j][0]
            G[j].remove(tmp)
            G[tmp].remove(j)
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
from scipy.sparse.csgraph import floyd_warshall

N, M = map(int, input().split())
graph = [[0 for _ in range(N)] for _ in range(N)]
ab = []
for _ in range(M):
    a1, b1 = map(int, input().split())
    ab.append([a1, b1])
    graph[a1-1][b1-1] = 1
    graph[b1-1][a1-1] = 1

ans = 0
for i, j in ab:
    d = copy.deepcopy(graph)
    d[i-1][j-1] = 0
    d[j-1][i-1] = 0
    d = floyd_warshall(d)
    for k in range(1,N):
        if d[0][k] == float("inf"):
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

    count = 0
    for a, b in AB:
        q = deque(maxlen=m)
        q.append(0)
        used = {0}
        while len(q) > 0:
            node = q.popleft()
            for to in g[node]:
                if to in used \
                    or node == a - 1 and to == b - 1 \
                    or node == b - 1 and to == a - 1:
                    continue
                q.append(to)
                used.add(to)
        if len(used) < n:
            count += 1

    return count

_n, _m = map(int, input().split())
_AB = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _AB))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=50
graph=[[False]*nmax for _ in range(nmax)]
visited=[False]*nmax

def dfs(n,v):
  visited[v]=True
  for v2 in range(n):
    if graph[v][v2]==False:
      continue
    if visited[v2]:
      continue
    dfs(n,v2)

def main():
  n,m=LI()
  a=[]
  b=[]
  for _ in range(m):
    _a,_b=LI()
    a.append(_a-1)
    b.append(_b-1)
    graph[_a-1][_b-1]=True
    graph[_b-1][_a-1]=True

  ans=0
  for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False

    for j in range(n):
      visited[j]=False

    dfs(n,j)

    bridge=False
    for j in range(n):
      if visited[j]==False:
        bridge=True
    if bridge:
      ans+=1

    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
"""
#N,K,Mが入力
    n,k,m=LI() 
    #N
    #x1 y1
    #.  .
    #xn ynが入力
    N=I()
    p=LIR(N)
    print(n,k,m,p)
"""
def resolve():
    n,m=LI()
    s=LIR(m)
    ans=0
    for i in range(m):
        uf=UnionFind(n)
        for j in range(m):
            if i!=j:
                a,b=s[j][0],s[j][1]
                uf.union(a,b)

        if len(uf.roots())>2:
            ans+=1

    print(ans)
    return
"""
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7
        output = 4
"""


############################## ユニオン木(union tree) ###################################
#uf=UnionFind(n)と使う
# print(uf.roots())
# print(uf.all_group_members())
class UnionFind:
    def __init__(self, n):
        self.n=n
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)#素集合でないとrankは意味がなさそう,素集合であればrank kには少なくとも2^k要素がある。
    
    # 検索
    def find(self, x):
        if self.par[x] == x:
        #if self.par[x] <0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(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(self, x, y):
        return self.find(x) == self.find(y)

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

    #すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.par) if i==x]

    #グループの数を返す
    def group_count(self):
        return len(self.roots())

    #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {int(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())
    

#辞書やタプルで使えるようにクラスを継承 l = ['A', 'B', 'C', 'D', 'E']とかを想定
class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * (self.n)
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

    #def size(self, x):
    #    return super().size(self.d[x])

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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



import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 3
1 2
1 3
2 3"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6 5
1 2
2 3
3 4
4 5
5 6"""
        output = """5"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

G =[[] for _ in range(n)]
E=[]
for i in range(m):
    ai,bi = map(int, input().split( ))
    ai-=1;bi-=1
    G[ai].append(bi)
    G[bi].append(ai)
    E.append((ai,bi))

#橋検出のライブラリを探してもいいが
#n~50と点数的に愚直にやってみる
ans = 0
from collections import deque
for i in range(m):
    V = [0]*n
    Q = deque()
    Q.append(0)
    V[0] = 1
    while Q:
        v = Q.popleft()
        for u in G[v]:
            if (E[i] != (v,u) and E[i]!= (u,v)) and not V[u]:
                V[u]=1
                Q.append(u)
    if 0 in V:
        ans += 1
print(ans)

Submission status: Accepted

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

from collections import deque

def bfs(x):
  q=deque()
  q.append(x)
  while len(q):
    x=q.popleft()
    
    if P[x]==0:
      for i in B[x]:
        q.append(i)
        P[x]=1
        
ans=0
for a,b in A:
  P=[0]*N
  B[a-1].remove(b-1)
  B[b-1].remove(a-1)
  bfs(0)
  if P!=[1]*N:
    ans+=1
  B[a-1].append(b-1)
  B[b-1].append(a-1)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
ans = []
for i in range(m):
    G = [[] for _ in range(n)]
    for ii, jj in enumerate(a):
        if ii != i:
            j, k = jj
            j -= 1
            k -= 1
            G[j].append(k)
            G[k].append(j)
    #print(G)

    visit = [False] * n


    def dfs(p, visit):
        visit[p] = True
        for p2 in G[p]:
            if visit[p2]:
                continue
            dfs(p2, visit)


    dfs(0, visit)
    if all(visit):
        pass
    else:
        ans.append(i)
print(len(ans))

Submission status: Accepted

Solution code:
import queue
n,m = map(int,input().split())
g = [[] for _ in range(n)]
edge = []
for _ in range(m):
  a,b = map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
  edge.append([a-1,b-1])

def bfs(u,v):
  is_visited = [False]*n
  que = queue.Queue()
  is_visited[0] = True
  que.put(0)
  while not que.empty():
    cur = que.get()
    for i in g[cur]:
      if is_visited[i]==True: continue
      if cur==u and i==v: continue
      if cur==v and i==u: continue
      is_visited[i] = True
      que.put(i)
  return all(is_visited)

c = 0
for i,j in edge:
    if not bfs(i,j): 
      c += 1
print(c)

Submission status: Accepted

Solution code:
def root(v):
    if v == par[v]:
        return v
    par[v] = root(par[v])
    return par[v]

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        par[u] = v
    else:
        par[v] = u
        if rank[u] == rank[v]:
            rank[u] += 1

def bridge(u, v):
    return root(u) != root(v)

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    par = list(range(N))
    rank = [0] * N
    tmp_E = E[:i] + E[i+1:]
    for a, b in tmp_E:
        unite(a-1, b-1)
    a, b = E[i]
    ans += bridge(a-1, b-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    gone = [False for i in range(n+1)]
    gone[0] = True
    stack = [v]
    gone[v] = True
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if gone[w] == False:
                stack.append(w)
            gone[w] = True
    return (False in gone)

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
lis = [list(map(int,input().split())) for i in range(m)]
ans = 0
for i in range(m):
    graph[lis[i][0]].append(lis[i][1])
    graph[lis[i][1]].append(lis[i][0])

for i in range(m):
    graph[lis[i][0]].remove(lis[i][1])
    graph[lis[i][1]].remove(lis[i][0])
    if dfs(1):ans += 1
    graph[lis[i][0]].append(lis[i][1])
    graph[lis[i][1]].append(lis[i][0])

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy


def dfs(v):
    visited[v] = 1
    ret = 1
    for w in r[v]:
        if visited[w] == 1:
            continue
        ret += dfs(w)
        visited[w] = 1
    return ret


n,m = map(int,input().split())
x = [[] for _ in range(n)]
x_list = []
cnt = 0
for _ in range(m):
    a,b = map(int,input().split())
    x_list.append([a-1,b-1])
    x[a-1].append(b-1)
    x[b-1].append(a-1)
for i in range(m):
    r = deepcopy(x)
    r[x_list[i][0]].remove(x_list[i][1])
    r[x_list[i][1]].remove(x_list[i][0])
    visited = [0]*n
    if dfs(0) == n:
        cnt += 1
print(m-cnt)

Submission status: Accepted

Solution code:
from copy import deepcopy


def dfs(v):
    visited[v] = 1
    ret = 1
    for w in range(n):
        if [v, w] not in r:
            continue
        elif visited[w] == 1:
            continue
        ret += dfs(w)
        visited[w] = 1
    return ret


n,m = map(int,input().split())
x = []
cnt = 0
for _ in range(m):
    a,b = map(int,input().split())
    x.append([a-1,b-1])
    x.append([b-1, a-1])
for i in range(m):
    r = deepcopy(x)
    r.pop(2*i)
    r.pop(2*i)
    visited = [0]*n
    if dfs(0) == n:
        cnt += 1
print(m-cnt)

Submission status: Accepted

Solution code:
from copy import deepcopy


def dfs(v, n, r, visited):
    visited[v] = 1
    ret = 1
    for w in range(n):
        if [v, w] not in r:
            continue
        elif visited[w] == 1:
            continue
        ret += dfs(w, n, r, visited)
        visited[w] = 1
    return ret


n,m = map(int,input().split())
x = []
cnt = 0
for _ in range(m):
    a,b = map(int,input().split())
    x.append([a-1,b-1])
    x.append([b-1, a-1])
for i in range(m):
    r = deepcopy(x)
    r.pop(2*i)
    r.pop(2*i)
    visited = [0]*n
    if dfs(0, n, r, visited) == n:
        cnt += 1
print(m-cnt)

Submission status: Accepted

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

import queue

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

for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    edges.append( (a, b) )

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

def bfs(u, v):
    is_visited = [ False ]*n
    que = queue.Queue() 
    is_visited[0] = True
    que.put(0)

    while not que.empty():
        cur = que.get()
        for adj in graph[cur]:
            if is_visited[adj]: continue
            if cur == u and adj == v: continue
            if cur == v and adj == u: continue
            is_visited[adj] = True
            que.put(adj)

    return all(is_visited)

ans = 0
for u, v in edges:
    if not bfs(u, v):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = 0
for i in range(M):
    queue = deque([1])
    checked = [0]*(N+1)
    checked[1] = 1
    NG = {edges[i][0],edges[i][1]}
    
    while queue:
        currentpoint = queue.popleft()
        for nextpoint in connections[currentpoint]:
            if not (currentpoint in NG and nextpoint in NG) and checked[nextpoint] == 0:
                queue.append(nextpoint)
                checked[nextpoint] = 1
            
    if sum(checked) != N:
        ans += 1
        
print(ans)

Submission status: Accepted

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

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

for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    edges.append( (a, b) )

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

def dfs(u, v):
    is_visited = [ False ]*n
    st = []
    is_visited[0] = True
    st.append(0)

    while st:
        cur = st.pop()
        for adj in graph[cur]:
            if is_visited[adj]: continue
            if cur == u and adj == v: continue
            if cur == v and adj == u: continue
            is_visited[adj] = True
            st.append(adj)

    return all(is_visited)

ans = 0
for u, v in edges:
    if not dfs(u, v):
        ans += 1

print(ans)

Submission status: Accepted

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

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

edges = []
graph = [ [] for _ in range(n) ]

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

def dfs(cur, u, v):
    is_visited[cur] = True
    for adj in graph[cur]:
        if is_visited[adj]: continue
        if cur == u and adj == v: continue
        if cur == v and adj == u: continue
        
        dfs(adj, u, v)

ans = 0
for u, v in edges:
    is_visited = [False]*n
    dfs(0, u, v)
    if not all(is_visited):
        ans += 1

print(ans)