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:
def search(t, i, reached):
    if reached[i]:
        return

    reached[i] = True
    for nt in t[i]:
        search(t, nt, reached)


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

    t = [[] for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        t[a].append(b)
        t[b].append(a)

    cnt = 0
    for a, b in AB:
        a -= 1
        b -= 1

        t[a].remove(b)
        t[b].remove(a)
        reached = [False for _ in range(N)]
        search(t, 0, reached)
        if not all(reached):
            cnt += 1

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

    print(cnt)


main()

Submission status: Accepted

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

from collections import defaultdict
ans = 0
for i in range(m):
    visited = [0] * n

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

    stack = [0]
    while stack:
        start = stack.pop()
        for target in graph[start]:
            if visited[target] == 0:
                visited[target] = 1
                stack.append(target)

    if sum(visited) != n:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
graph = [[0]*N for i in range(N)]
vstd = [0] * N

for i in range(M):
    a, b = [int(i) for i in input().split()]
    graph[a-1][b-1] = graph[b-1][a-1] = 1
#print(*graph, sep="\n")

def dfs(v):
    vstd[v] = 1
    for v2 in range(N):
        if graph[v][v2] == 0:
            continue
        if vstd[v2] == 1:
            continue
        dfs(v2)
 
ans = 0
for i in range(N):
    for j in range(N):
        if graph[i][j] == 0:
            continue
        graph[i][j] = graph[j][i] = 0
        for k in range(N):
            vstd[k] = 0
        dfs(0)
        bridge = False
        for k in range(N):
            if vstd[k] == 0:
                bridge = True
        if bridge == True:
            ans += 1
        graph[i][j] = graph[j][i] = 1

print(ans//2)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
li = []
count = 0

def check_dfs(node_list):
    traveled = []
    return dfs(node_list, traveled, 0)


def dfs(node_list, t_list, position):
    t_list.append(position)
    if len(t_list) == n:
        return 0
    for i in node_list[position]:
        if i not in t_list:
            dfs(node_list, t_list, i)
    if len(t_list) == n:
        return 0
    else:
        return 1

for i in range(m):
    array = list(map(int, input().split()))
    li.append(array)

for i in range(m):
    nodes = [[] for k in range(n)]
    for j in range(m):
        if j == i:
            continue
        else:
            nodes[li[j][0]-1].append(li[j][1]-1)
            nodes[li[j][1]-1].append(li[j][0]-1)
    count += check_dfs(nodes)

print(count)

Submission status: Accepted

Solution code:
from collections import deque

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

graph=[[False]*N for i in range(N)]
visited=[False]*N
a=[0]*M
b=[0]*M

for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=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
    d=deque([0])
    while d:
        temp=d.popleft()
        visited[temp]=True
        for j in range(N):
            if graph[temp][j]==True and visited[j]==False:
                d.append(j)

    bridge = False
    for j in range(N):
        if visited[j] == False:
            bridge = True
            break
    if bridge == True:
        ans += 1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Submission status: Accepted

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

graph=[[False]*N for i in range(N)]
visited=[False]*N
a=[0]*M
b=[0]*M

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


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

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(0)
    bridge=False
    for j in range(N):
        if visited[j]==False:
            bridge=True
    if bridge==True:
        ans+=1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Submission status: Accepted

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

C=[[] for i in range(N)]

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

cnt=0
f=True
while f:
    f=False
    for i in range(N):
        if len(C[i])==1:
            cnt+=1
            idx=C[C[i][0]].index(i)
            C[C[i][0]].pop(idx)
            C[i].pop()
            f=True
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(bu, bv, u=0):
        for cu in to[u]:
            if (u, cu) == (bu, bv) or (u, cu) == (bv, bu): continue
            if fin[cu]: continue
            fin[cu] = True
            dfs(bu, bv, cu)

    to = defaultdict(list)
    ee = []
    n, m = MI()
    for _ in range(m):
        a, b = map(int1, input().split())
        to[a].append(b)
        to[b].append(a)
        ee.append([a, b])
    ans = 0
    for u, v in ee:
        fin = [False] * n
        fin[0] = True
        dfs(u, v)
        if sum(fin) < n: ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
# たまにはDFSでグラフを全探索する
from collections import deque

N,M=map(int,input().split())
out=[set() for v in range(N+1)];out[0]=None
es=[None]
for e in range(1,M+1):
    a,b=map(int,input().split())
    es.append((a,b))
    out[a].add(b);out[b].add(a)

# print(es) #DB
# print(out) #DB

ans=0
q=deque()
for e in es[1:]: # 各辺を順にチェックする
    r=[False for v in range(N+1)];out[0]=None # 到達フラグ
    a,b=e # 着目している辺の始点と終点
    r[a]=True # 始点に到達する
    for u in out[a]-{b}:
        q.append(u);r[u]=True # 始点と繋がっている終点以外の頂点を全てスタックに入れ，到達する
    while q:
        u=q.pop() # LIFO
        for v in out[u]:
            if not r[v]:
                q.append(v);r[v]=True
    if not r[b]: # 終点（頂点b）に到達していなければ，辺(a,b)は橋であった
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
edges = [list(map(int,input().split())) for i in range(M)]
ans = 0
for x in edges:
  l = list(range(N))
  for y in edges:
    if y!=x:
      l=[l[y[0]-1] if l[i]==l[y[1]-1] else l[i] for i in range(N)]
  if len(set(l))!=1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y): # xとyの属する集合を併合
    x=find(x)
    y=find(y)
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

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

def main():
    n,m=inpm()
    ab=[]
    for _ in range(m):
        a,b=inpm()
        ab.append((a-1,b-1))
    ans=0
    global par,rank
    for i in range(m):
        par=[k for k in range(n)]  # 親
        rank=[0 for _ in range(n)] # 木の深さ
        for j in range(m):
            if i==j:
                continue
            unite(ab[j][0],ab[j][1])
        for j in range(n-1):
            if not same(j,j+1):
                ans+=1
                break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

graph = [[] for i in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

ans = 0

for i in ab:
    start = i[0]
    last = i[1]
    
    que = [start]
    visit = [False]*(n+1)
    visit[start]=True
    while que:
        q = que.pop()
        for j in graph[q]:
            if q == start and j== last:
                continue
            if j==last:
                break
            if  not visit[j]:
                que.append(j)
                visit[j] = True
        else:
            continue
        break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# 葉頂点のインデックスを取得する
def search_leaf(edge_list):
    for i in range(N):
        if len([j for j in edge_list[i] if j]) == 1:
            return i
    # 葉頂点がない場合
    return N

N, M = map(int,input().split())
E = [[False for i in range(N)] for j in range(N)]

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

answer = 0

for i in range(N):
    V = search_leaf(E)
    if V == N: break
    
    # 橋を壊す
    main_land = E[V].index(True)
    E[V][main_land] = E[main_land][V] = False

    answer += 1

print(answer)

Submission status: Accepted

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

for i in range(M):
	# bfs
	Q = [0]
	visited = [False for _ in range(N)]
	while Q:
		if all(visited): break
		cur_v = Q.pop(0)
		visited[cur_v] = True
		for adj_v in adj[cur_v]:
			if visited[adj_v] == False:
				# print(cur_v, adj_v, E[i])
				if (cur_v != E[i][0] or adj_v != E[i][1]) and (cur_v != E[i][1] or adj_v != E[i][0]):
					visited[adj_v] = True
					Q.append(adj_v)
	# print(visited)
	if all(visited):
		ans += 1
		
print(M - ans)

Submission status: Accepted

Solution code:
# ABC075 C - Bridge
def dfs(v):
    visited[v]=True
    for nv in range(n):
        if G[v][nv]==False:
            continue
        if visited[nv]:
            continue
        dfs(nv)

n,m = map(int,input().split())
G = [[False]*n for _ in range(n)]
ans = 0
visited = [False for _ in range(n)]
A,B = [],[]
for i in range(m):
    a,b = map(int,input().split())
    A.append(b-1)
    B.append(a-1)
    G[a-1][b-1]=G[b-1][a-1]=True

for i in range(m):
    G[A[i]][B[i]]=G[B[i]][A[i]]=False
    visited = [False for _ in range(n)]
    dfs(0)
    if all(visited):
        ans += 1
    G[A[i]][B[i]]=G[B[i]][A[i]]=True

print(m-ans)

Submission status: Accepted

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

N, M = map(int, input().split())
k = [[] for _ in range(N)]
flst = [list([0] * 2) for _ in range(M)]

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

d = [0] * N
def dfs(v):
    d[v] = 1
    for i in range(len(k[v])):
        if d[k[v][i]] == 0:
            dfs(k[v][i])
    return
ans = 0
for i in range(M):
    tmp1 = k[flst[i][0] - 1].index(flst[i][1] - 1)
    tmp2 = k[flst[i][1] - 1].index(flst[i][0] - 1)
    k[flst[i][0] - 1].pop(tmp1)
    k[flst[i][1] - 1].pop(tmp2)
    dfs(0)
    if sum(d) != N:
        ans += 1

    d = [0] * N
    k[flst[i][0] - 1].append(flst[i][1] - 1)
    k[flst[i][1] - 1].append(flst[i][0] - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0
for i in range(m):
  litmp = [[] for _ in range(n)]
  for j in range(m):
    if j != i:
      a = liv[j][0]
      b = liv[j][1]
      litmp[a-1].append(b-1)
      litmp[b-1].append(a-1)
  seen = [False]*n
  todo = deque([])
  seen[0] = True
  todo.append(0)
  while len(todo) > 0:
    v = todo.pop()
    for vn in litmp[v]:
      if not seen[vn]:
        seen[vn] = True
        todo.append(vn)
  #print(seen)
  #print(todo)
  for j in range(n):
    if seen[j]:
      continue
    else:
      ans += 1
      break
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]

li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
nu = []

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    #k：中継
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        if inf in i:
            point += 1
            break
print(point)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dd = [[False]*n for _ in range(n)]
visited = [False]*n

a=[]
b=[]

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

def dfs(v):
  visited[v] = True
  for v2 in range(n):
    if dd[v][v2] == False:
      continue
    if visited[v2] == True:
      continue
    dfs(v2)  
    
ans = 0
for i in range(m):
  dd[a[i]][b[i]] = dd[b[i]][a[i]] = False  
  
  for j in range(n):
    visited[j] = False
    
  dfs(0)
  
  if sum(visited) == n:
    ans +=1
    
  dd[a[i]][b[i]] = dd[b[i]][a[i]] = True
  
  
print(m-ans)

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()]
ablist = []
nodelist = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b = [int(i)-1 for i in input().split()]
    ablist.append([a,b])
    nodelist[a][b] = 1
    nodelist[b][a] = 1

#print(nodelist)

ans = 0

for a,b in ablist:
    #print(a,b)
    newnodelist = [[nodelist[i][j] for i in range(N)] for j in range(N)]
    newnodelist[a][b]=0
    newnodelist[b][a]=0
    #print(newnodelist)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if newnodelist[i][k]&newnodelist[k][j]==1:
                    newnodelist[i][j]=1
    #print(newnodelist)
    a = sum([sum(i) for i in newnodelist])
    #print(a)
    if a!= N*N:
        ans+=1
        
print(ans)

Submission status: Accepted

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

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy

def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

ans=0
for i in range(M):
    if len(set((UF_make(AB[:i]+AB[i+1:],N))))!=1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def par(a):
    if P[a] == a: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    P[par(b)] = par(a)

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

ans = 0
for i in range(M):
    P = [i for i in range(N)]
    for j in range(M):
        if i != j:
            unite(X[j][0], X[j][1])
    if sum([1 if par(i) == i else 0 for i in range(N)]) > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [float("inf")]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
#            if nowv == W[ne]:
                #ループが嫌な時
#                return -1
            if W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return len
def examC(inf):
    N, M = LI()
    ab = [[] for i in range(M)]
    for i in range(M):
        ab[i] = LI()
    cur = 0
    for i in range(M):
        v = [[] for i in range(N)]
        for j in range(M):
            if j!=i:
                v[ab[j][0] - 1].append(ab[j][1] - 1)
                v[ab[j][1] - 1].append(ab[j][0] - 1)
        B  = bfs(N,0,v)
#        print(B)
        if inf in B:
            cur +=1
    print(cur)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC(inf)

Submission status: Accepted

Solution code:
import copy
N,M=map(int,input().split())
A=[]

for i in range(M):
    a,b=map(int,input().split())
    A.append([a,b])
    
ANS=0
for i in range(M):
    L=[[]for _ in range(N+1)]
    for j in range(M):
        if i==j:
            continue
        else:
            L[A[j][0]].append((A[j][1],A[j][0]))
            L[A[j][1]].append((A[j][0],A[j][1]))
    X=1
    C=[100 for i in range(N+1)]
    C[1]=1
    C[0]=1
    Q=L[1]
    #print(L)
    for j in range(1000):
        if len(Q)==j:
            break
        if C[Q[j][0]]==100:
            C[Q[j][0]]=C[Q[j][1]]+1
            for k in L[Q[j][0]]:
                if C[k[0]]==100:
                    Q.append((k[0],k[1]))
    #print(Q)
    #print(C)
    if 100 in C:
        ANS+=1
print(ANS)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]

    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


n, m = ril()
ls = rils(m)

count = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        a, b = ls[j]
        uf.merge(a - 1, b - 1)
    for i in range(n):
        uf.get_root(i)
    if len(set(uf.parents)) > 1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[False] * N for _ in range(N)]
visited = [False] * N
sides = []


def dfs(node):
    if visited[node]:
        return
    
    visited[node] = True

    for i in range(N):
        if graph[node][i]:
            dfs(i)


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

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

print(ans)

Submission status: Accepted

Solution code:
"""
union-find木
"""


class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n

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


def abc120_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]

    ans = 0
    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if i == j:
                continue
            uf.unite(ab[j][0] - 1, ab[j][1] - 1)

        s = set()
        for j in range(n):
            s.add(uf.find(j))
        if len(s) > 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    abc120_d()

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int, input().split())
E = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    E[a-1].append((b-1, i))
    E[b-1].append((a-1, i))
    
ans = 0
for i in range(M):
    used = [0]*N
    q = deque()
    if i == 0:
        used[1] = 1
        q.append(1)
    else:
        used[0] = 1
        q.append(0)
    while q:
        t = q.popleft()
        for L in E[t]:
            j = L[0]
            e = L[1]
            if used[j] == 0 and e != i:
                q.append(j)
                used[j] = 1
    if sum(used) < N:
        ans += 1
        
print(ans)

Submission status: Accepted

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

def walk(cur):
    visited[cur] = True
    for i in range(N):
        if g[cur][i] and not visited[i]:
            walk(i)
        else:
           continue

ans = 0
for i in range(M):
    g[A[i]][B[i]] = False
    g[B[i]][A[i]] = False
    visited = [False] * N
    walk(0)
    if not all(visited):
        ans += 1
    g[A[i]][B[i]] = True
    g[B[i]][A[i]] = True

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 + 1)]

for i in range(m):
    B[A[i][0]].append(A[i][1])
    B[A[i][1]].append(A[i][0])

co = 0
ok = 0
while ok == 0:
    ok = 1
    for i in range(1, n + 1):
        if len(B[i]) == 1:
            ok = 0
            k = B[i][0]
            B[i].remove(k)
            B[k].remove(i)
            co += 1

print(co)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    d = collections.defaultdict(list)
    ab = []
    for i in range(m):
        a, b = list(map(int, readline().split()))
        d[a-1] += [b-1]
        d[b-1] += [a-1]
        ab.append(sorted([a-1, b-1]))
    cnt = 0
    for abl in ab:
        ql = collections.deque()
        ql.append(0)
        fq = collections.defaultdict(list)
        fq[0]
        a, b = abl
        while ql:
            q = ql.popleft()
            for v in d[q]:
                if v not in fq and [a, b] != sorted([q, v]):
                    ql.append(v)
                    fq[v]
        cnt += 1 if len(fq) != n else 0
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
xs=[tuple(map(int,input().split())) for _ in range(m)]
c=0
def root(n):
  if union[n]==n:
    return n
  union[n]=root(union[n])
  return union[n]
for i in range(m):
  union={x:x for x in range(1,n+1)}
  t=0
  for j in range(i):
    x,y=xs[j]
    union[root(x)]=root(y) 
  for j in range(i+1,m):
    x,y=xs[j]
    union[root(x)]=root(y) 
  for k in range(1,n+1):
    if union.get(k)==k:
      t+=1
  if t!=1:
    c+=1
print(c)

Submission status: Accepted

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

G=[[0]*n for i in range(n)]
V=[0 for i in range(n)]

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

def dfs(v):
	V[v]=1
	for v2 in range(n):
		if G[v][v2]==1 and V[v2]==0:
			dfs((v2))
			
ans=0
for i in range(m):
	G[A[i]][B[i]]=G[B[i]][A[i]]=0
	V=[0 for i in range(n)]
	dfs(0)
	if sum(V)!=n:
		ans+=1
	G[A[i]][B[i]]=G[B[i]][A[i]]=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M =map(int, input().split())
G  = [[[] for _ in range(N)] for __ in range(M)]
visit = [0]*N
for i in range(M):
    a,b = map(int, input().split())
    for j in range(M):
      if i != j:
        G[j][a-1].append(b)
        G[j][b-1].append(a)
    
def dfs(v,goal,G,visit):
    visit[v-1]=1 
    if visit[goal-1]:
        return True 
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        if dfs(next,goal,G,visit) == True:
            return True
    return False
  
comb = list(itertools.combinations(range(1,N+1),2))
count = 0

for g in G:
  flag = False
  for c in comb:
    visit = [0]*N  
    if not dfs(c[0],c[1],g,visit):
      flag = True
  if flag:
    count += 1
  
print(count)

Submission status: Accepted

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

N, M = [int(x) for x in input().strip().split()]
sides = [tuple([int(x) - 1 for x in input().strip().split()]) for _ in range(M)]

ans = 0
for i in range(M):
    node_N = [0] * N
    MAP = [[0] * N for _ in range(N)]
    sub_sides = [side for j, side in enumerate(sides) if j != i]
    for a, b in sub_sides:
        MAP[a][b] = 1
        MAP[b][a] = 1
    queue = [i for i, b in enumerate(MAP[0]) if b == 1]
    node_N[0] = 1
    while len(queue):
        p = queue.pop(0)
        if node_N[p] == 1:
            continue
        node_N[p] = 1
        queue.extend([i for i, b in enumerate(MAP[p]) if b == 1 and node_N[i] == 0])
    if 0 in node_N:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
n, m, *ab = (int(x) for x in sys.stdin.read().split())

bridges = 0
still_exist = True
while still_exist:
    bef = len(ab)
    for vertex, edges_count in Counter(ab).items():
        if edges_count == 1:
            i = ab.index(vertex)
            if i % 2 == 0: del ab[i:i+2]
            else: del ab[i-1:i+1]
            bridges += 1
            break 
    aft = len(ab)
    if bef == aft: still_exist = False

print(bridges)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Branch = [list(map(int,input().split())) for i in range(M)]
Glaph = [[0 for i in range(N)] for i in range(N)]
for b in Branch:
  Glaph[b[0]-1][b[1]-1] = 1
  Glaph[b[1]-1][b[0]-1] = 1
Visited = [0 for i in range(N)]
  
def dfs(v,N,Visited):
  flag = True
  for i in range(N):
    if Visited[i] == 0:
      flag = False
  if flag:
    return 1
  
  ret = 0
  
  for i in range(N):
    if Glaph[v][i] == False: continue
    if Visited[i]: continue    
    Visited[i] = 1    
    dfs(i,N,Visited)
  
  return Visited

ans = 0
for b in Branch:
  for i in range(N):
    Visited[i] = 0
  Visited[b[0]-1] = 1
  
  Glaph[b[0]-1][b[1]-1] = 0
  Glaph[b[1]-1][b[0]-1] = 0
  
  Visited = dfs(b[0]-1,N,Visited)
  
  Glaph[b[0]-1][b[1]-1] = 1
  Glaph[b[1]-1][b[0]-1] = 1
  
  if Visited[b[1]-1] == 0:
    ans += 1
  
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

matrix = [[0 for i in range(N)] for j in range(N)]

edge_list = []

for i in range(M):
    a, b = map(int, input().split())
    edge_list.append((min(a, b)-1, max(a, b)-1))
    matrix[min(a, b)-1][max(a, b)-1] = 1
    matrix[max(a, b)-1][min(a, b)-1] = 1
    
count = 0
    
for edge in edge_list:
    visited = [0] * N
    matrix[edge[0]][edge[1]] = 0
    matrix[edge[1]][edge[0]] = 0
    queue = deque()
    
    queue.append(0)
    visited[0] = 1
    
    while len(queue) > 0:
        target = queue.popleft()
        for i in range(N):
            if matrix[target][i] == 1 and visited[i] == 0:
                queue.append(i)
                visited[i] = 1

    if sum(visited) != N:
        count += 1
        
    matrix[edge[0]][edge[1]] = 1
    matrix[edge[1]][edge[0]] = 1
    

print(str(int(count)))

Submission status: Accepted

Solution code:
from scipy.sparse import *
N,M,*A=map(int,open(0).read().split());g=csr_matrix(([1]*M,(A[::2],A[1::2])),shape=(N+1,N+1)).tolil()
c = 0

for a,b in zip(*g.nonzero()):
  g[a,b]=0
  n,_=csgraph.connected_components(g)
  c+=n!=2
  g[a,b]=1

print(c)