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.

Solution (Python):
import math
import bisect
import collections
import itertools
import sys
sys.setrecursionlimit(100000000)
def gcd(a,b):return math.gcd 
def lcm(a,b):return (a*b) // math.gcd(a,b) 
def iin(): return int(input()) 
def imn(): return map(int, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def comb(l, n): return itertools.combinations(l, n) 
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: divisors.append(n//i)
    return divisors
def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False 
    return True

N,M=imn()
a = []
b = []
visited = [False for _ in range(N)]
graph = [[False for _ in range(50)] for _ in range(50)]
    
for i in range(M):
    v1,v2 = map(lambda x:int(x)-1, input().split())
    a.append(v1)
    b.append(v2)
    graph[v1][v2] = graph[v2][v1] = True

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

ans = 0

for i in range(M):
    v1 = a[i]
    v2 = b[i]
    graph[v1][v2] = graph[v2][v1] = False
    
    for i in range(N): visited[i] = False

    dfs(0)
    
    for j in range(N):
        if visited[j] == False:
            ans += 1
            break

    graph[v1][v2] = graph[v2][v1] = True

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)  

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


def rel_side(v, G):  
  if all(vis):
    return 1
  r = 0
  for side in G[v]:
    if not vis[side]:
      vis[side] = True
      r += rel_side(side, G)
  return r


bridge = 0
for i in range(N):
  for j, k in enumerate(G[i]):
    vis = [False] * N
    vis[i] = True
    pop1 = G[i].pop(j)
    idx = G[pop1].index(i)
    pop2 = G[pop1].pop(idx)
    if not rel_side(i, G):
      bridge += 1
    
    G[i].insert(j, pop1)
    G[pop1].insert(idx, pop2)
    

print(bridge // 2)

Solution (Python):
import sys
import copy

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

V = []
E = []
seen = [False]*N
count = 0

for _ in range(N):
    V.append(set())

for _ in range(M):
    *l, = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0]-1,l[1]-1])

V_copy = copy.deepcopy(V)
seen_copy = copy.deepcopy(seen)

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

    for next_node in V[node]:
        dfs(next_node)

for i in range(len(E)):
    V[E[i][1]].remove(E[i][0])
    V[E[i][0]].remove(E[i][1])
    dfs(0)

    if (False in seen)==True:
        count = count + 1
    seen = copy.deepcopy(seen_copy)
    V = copy.deepcopy(V_copy)

print(count)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def reach_all(G, N):
    visited = [0] * N
    def dfs(G, v):
        visited[v] = 1
        for next_v in G[v]:
            if visited[next_v]:
                continue
            dfs(G, next_v)
    dfs(G, 0)
    if sum(visited) != N:
        return False
    return True

def main():
    N, M = LI()
    edge = []
    for _ in range(M):
        a, b = LI_()
        edge.append((a, b))

    cnt = 0
    for i in range(M):
        G = [[] for _ in range(N)]
        for j in range(M):
            if i == j:
                continue
            a, b = edge[j]
            G[a].append(b)
            G[b].append(a)
        if not reach_all(G, N):
            cnt += 1
    print(cnt)
main()

Solution (Python):
import sys, copy
sys.setrecursionlimit(100)

def g(mat, ind):
  return [k for k in range(len(mat)) if mat[ind][k]==1]

def f(mat, ind, sumi):
  sumi[ind]=1
  linknode=g(mat, ind)
  for j in linknode:
    if sumi[j]==0:
      sumi=f(mat, j, sumi)
  return sumi

N, M=map(int, input().split())
ab=[list(map(int, input().split())) for i in range(M)]
net=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
  net[ab[i][0]][ab[i][1]]=1
  net[ab[i][1]][ab[i][0]]=1
  
counter=0
for i in range(M):
  temp=copy.deepcopy(net)
  temp[ab[i][0]][ab[i][1]]=0
  temp[ab[i][1]][ab[i][0]]=0
  if sum(f(temp, 1, [0]*(N+1)))!=N:
    counter+=1
print(counter)

Solution (Python):
import sys
import copy




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

seen = [False]*N
V = []
E = []

def dfs(node):
    global V
    global seen

    if seen[node]==True:
        return
    if not (False in seen):
        return
    seen[node]=True

    for next_node in V[node]:
        dfs(next_node)

    return

for i in range(N):
    V.append(set())
    
for i in range(M):
    *l,  = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0]-1, l[1]-1])

seen_copy = copy.deepcopy(seen)
V_copy    = copy.deepcopy(V)
count = 0

for edge in E:
    V[edge[0]].remove(edge[1])
    V[edge[1]].remove(edge[0])

    dfs(0)

    if (False in seen):
        count = count + 1

    seen = copy.deepcopy(seen_copy)
    V    = copy.deepcopy(V_copy)

print(count)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = []
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    edges.append((a, b))

def check(x):
    nodes = [[] for i in range(N)]
    for i in range(M):
        
        if i == x:
            continue
        a, b = edges[i]
        nodes[a].append(b)
        nodes[b].append(a)
    
    que = deque([0])
    visited = [0] * N
    while que:
        u = que.popleft()
        if visited[u]:
            continue
        visited[u] = 1
        for v in nodes[u]:
               que.append(v)
    
    return sum(visited) != N

ans = 0
for x in range(M):
    
    if check(x):
        ans += 1
print(ans)

Solution (Python):

n,m=map(int,input().split())
A=[list(map(int,input().split()))for i in range(m)]
d=[[float('inf') for i in range(n)]for i in range(n)]

def wf(d):
    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[j][k])








count=0
for i in range(m):
    d=[[float('inf') for _ in range(n)]for _ in range(n)]
    for j in range(m):
        if i==j:
            p,q=A[j]
            p-=1
            q-=1
            
        else:
            a,b=A[j]
            a-=1
            b-=1
            d[a][b]=1
            d[b][a]=1
    wf(d)
    if d[p][q]==float('inf'):
        count+=1
print(count)

Solution (Python):

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



def find(x):
    
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    
    
    x=find(x)
    y=find(y)
    if x==y:
        return False
    else:
        if par[x]>par[y]:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
def same(x,y):
    
    return find(x)==find(y)
def size(x):
    return -par[x]


c=0
for i in range(m):
    par=[-1]*n
    for j in range(m):
        if i==j:
            r,s=A[j]
            r-=1
            s-=1
        else:
            p,q=A[j]
            p-=1
            q-=1
            unite(p,q)
    if same(r,s)==False:
        c+=1
print(c)

Solution (Python):
import sys
import copy


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

V = []
E = []

for i in range(N):
    V.append(set())

seen = []
seen = [False] * N

count = 0
def dfs(node):
    global V
    global seen

    
    if seen[node]==True:
        return
    
    seen[node]=True

    for next_node in V[node]:
        dfs(next_node)
    return

for i in range(M):
    *l,  = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0]-1, l[1]-1])



E_copy = copy.deepcopy(E)
V_copy = copy.deepcopy(V)
seen_copy = copy.deepcopy(seen)


for i in range(M):
    e = [E[i][0], E[i][1]]
    
    V[e[0]].remove(e[1])
    V[e[1]].remove(e[0])
    
    dfs(0)
    if (False in seen):
        count = count + 1
    seen = [False] * N
    V = copy.deepcopy(V_copy)
   
print(count)

Solution (Python):
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
ab = map(int, sys.stdin.read().split())
ab = zip(*[ab] * 2)
graph = [set() for _ in range(n+1)]
for a, b in ab:
    graph[a].add(b)
    graph[b].add(a)

def main():
    que = set()
    for i in range(1, n+1):
        if len(graph[i]) == 1:
            que.add(i)
    res = len(que)
    while que:
        x = que.pop()
        y = graph[x].pop()
        graph[y] -= set([x])
        l = len(graph[y])
        if l == 0:
            que -= set([y])
            res -= 1
        elif l == 1:
            que.add(y)
            res += 1

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
N, M = map(int, readline().split())
graph = [0 for i in range(N)]
ab = []
for i in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    ab.append([a, b])
    graph[a] |= 1 << b
    graph[b] |= 1 << a

all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (not graph[v] >> u & 1) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use

ans = 0
for a, b in ab:
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
    if rec(0, 0) != all_use:
        ans += 1
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
print(ans)

Solution (Python):
N, M = map(int, input().split())
graph = [0 for i in range(N)]
ab = []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ab.append([a, b])
    graph[a] |= 1 << b
    graph[b] |= 1 << a
all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (not graph[v] >> u & 1) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use

ans = 0
for a, b in ab:
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
    if rec(0, 0) != all_use:
        ans += 1
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
print(ans)

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

all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (not graph[u][v]) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use

ans = 0
for a, b in ab:
    graph[a][b] = graph[b][a] = False
    if rec(0, 0) != all_use:
        ans += 1
    graph[a][b] = graph[b][a] = True
print(ans)

Solution (Python):
N, M = map(int, input().split())
graph = [[] for i in range(N)]
alst, blst = [], []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    alst.append(a)
    blst.append(b)
    graph[a].append(b)
    graph[b].append(a)

all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (u not in graph[v]) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use


ans = 0
for a, b in zip(alst, blst):
    graph[a].remove(b)
    graph[b].remove(a)
    if rec(0, 0) != all_use:
        ans += 1
    graph[a].append(b)
    graph[b].append(a)
print(ans)

Solution (Python):
N, M = map(int,input().split())                                         
visited = [False for i in range(N)]                                     
edges = [[i-1 for i in map(int,input().split())] for j in range(M)]     
graph = [[False for i in range(N)] for j in range(N)]                   


for edge in edges:
    graph[edge[0]][edge[1]] = True
    graph[edge[1]][edge[0]] = True


def dfs(v):
    queue = [v]
    while len(queue) != 0:
        now = queue.pop()
        visited[now] = True
        for next in range(N):
            if graph[now][next] == False:continue
            if visited[next] == True:continue
            queue.append(next)

ans = 0


for i in range(M):
    graph[edges[i][0]][edges[i][1]] = False
    graph[edges[i][1]][edges[i][0]] = 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:
        ans += 1

    graph[edges[i][0]][edges[i][1]] = True
    graph[edges[i][1]][edges[i][0]] = True

print(ans)

Solution (Python):
N, M = map(int,input().split())                                         
visited = [False for i in range(N)]                                     
edges = [[i-1 for i in map(int,input().split())] for j in range(M)]     
graph = [[False for i in range(N)] for j in range(N)]                   


for edge in edges:
    graph[edge[0]][edge[1]] = True
    graph[edge[1]][edge[0]] = True


def dfs(v):
    queue = [v]
    while len(queue) != 0:
        now = queue.pop(0)
        visited[now] = True
        for next in range(N):
            if graph[now][next] == False:continue
            if visited[next] == True:continue
            queue.append(next)

ans = 0


for i in range(M):
    graph[edges[i][0]][edges[i][1]] = False
    graph[edges[i][1]][edges[i][0]] = 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:
        ans += 1

    graph[edges[i][0]][edges[i][1]] = True
    graph[edges[i][1]][edges[i][0]] = True

print(ans)

Solution (Python):
N, M = map(int,input().split())                                         
visited = [False for i in range(N)]                                     
edges = [[i-1 for i in map(int,input().split())] for j in range(M)]     
graph = [[False for i in range(N)] for j in range(N)]                   


for edge in edges:
    graph[edge[0]][edge[1]] = True
    graph[edge[1]][edge[0]] = True


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

ans = 0


for i in range(M):
    graph[edges[i][0]][edges[i][1]] = False
    graph[edges[i][1]][edges[i][0]] = 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:
        ans += 1

    graph[edges[i][0]][edges[i][1]] = True
    graph[edges[i][1]][edges[i][0]] = True

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
n,m=map(int,input().split())
es=[[[] for j in range(n)] for i in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for j in range(m):
        if i!=j:
            es[j][a].append(b)
            es[j][b].append(a)
sw = [[True for i in range(n)] for i in range(m)]
def dfs(v,k):
    sw[k][v] = False
    for i in es[k][v]:
        if sw[k][i]:
            dfs(i,k)
for i in range(m):
    dfs(0,i)
ans=0
for j in range(m):
    for i in range(n):
        if sw[j][i]:
            ans+=1
            break
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
n,m=map(int,input().split())
es=[[[] for j in range(n)] for i in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for j in range(m):
        if i!=j:
            es[j][a].append(b)
            es[j][b].append(a)
sw = [[True for i in range(n)] for i in range(m)]
def dfs(v,k):
    sw[k][v] = False
    for i in es[k][v]:
        if sw[k][i]:
            dfs(i,k)
for i in range(m):
    dfs(0,i)
ans=0
for j in range(m):
    for i in range(n):
        if sw[j][i]:
            ans+=1
            break
print(ans)

Solution (Python):
def dfs(graph, visited, edge):
    visited[edge] = True

    for i in range(n):
        if graph[edge][i] == 1 and visited[i] == False:
            dfs(graph, visited, i)

    if sum(visited) == n: return True
    else: return False


n, m = map(int, input().split())
input_list = []
for i in range(m):
    input_list.append(list(map(int, input().split())))
    
cnt = 0
for skip in range(m):
    graph = [[0]*n for _ in range(n)]

    for stage in range(m):
        if stage == skip:
            continue

        i, j = input_list[stage]
        graph[i-1][j-1] = 1
        graph[j-1][i-1] = 1

    visited = [False for _ in range(n)]

    cnt += dfs(graph, visited, 0)        

print(m - cnt)

Solution (Python):
import copy

n, m = map(int, input().split())
Adj_dict_all = {} 
Input_ab_list = []

for i in range(n):
    new = {i+1: []}
    Adj_dict_all.update(new)


for _ in range(m):
    a, b = map(int, input().split())
    Adj_dict_all[a].append(b)
    Adj_dict_all[b].append(a)
    Input_ab_list.append((a,b))


def Connection(Adj_dict = {}, start = 1, Visited = [False]*n):

    if Visited[start-1]:
        return
    
    
    Visited[start-1] = True
    
    for node in Adj_dict[start]:
        if Visited[node-1] == False:
            Connection(Adj_dict, node, Visited)
    
    return

ans = 0


for i in range(m):
    
    del_a = Input_ab_list[i][0]
    del_b = Input_ab_list[i][1]

    
    Adj_dict = copy.deepcopy(Adj_dict_all)
    Adj_dict[del_a].remove(del_b)
    Adj_dict[del_b].remove(del_a)

    Visited=[False]*n
    Connection(Adj_dict, 1, Visited)

    
    if not all(Visited):
        ans += 1    

print(ans)

Solution (Python):
from collections import deque
n,m = map(int, input().split(' '))
AB = [list(map(int, input().split(' '))) for i in range(m)]
ans = 0
for X in range(m):
    graph = [[] for i in range(n+1)]
    for i in range(m):
        if i != X:
            [a,b] = AB[i]
            graph[a].append(b)
            graph[b].append(a)
    x = deque([1])
    visited = [0]*(n+1)
    while x:
        q = x.popleft()
        visited[q] = 1
        for i in graph[q]:
            if visited[i] == 0:
                x.append(i)
    for i in range(1,n+1):
        if visited[i] != 1:
            ans += 1
            break
print(ans)

Solution (Python):

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

    
    graph = []
    for _ in range(N):
        graph.append([False] * N)

    for a, b in AB:
        graph[a][b] = True
        graph[b][a] = True
        
    visited = [False] * N

    def dfs(v):
        """v（頂点）からスタートする"""

        
        if visited[v]:
            return

        
        visited[v] = True

        
        edges = graph[v]
        for i, e in enumerate(edges):
            if e:
                dfs(i)

        return


    ans = 0
        
    
    for a, b in AB:
        graph[a][b] = False
        graph[b][a] = False

        visited = [False] * N
        dfs(0)
        
        
        if not all(visited):
            ans += 1

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

    print(ans)

if __name__ == "__main__":
    main()

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

for edge_i in edges:
  check_list = [i for i in range(n)]
  for edge_j in edges:
    if edge_i != edge_j:
      check_list = [check_list[edge_j[0]-1] if check_list[i]==check_list[edge_j[1]-1] else check_list[i] for i in range(n)]
  if len(set(check_list))!=1:ans += 1
      
print(ans)

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

MAP=[[0]*N for i in range(N)]
S=[0]*N
for i in range(M):
    a,b=map(int,input().split())
    MAP[a-1][b-1]+=1
    MAP[b-1][a-1]+=1
    S[a-1]+=1
    S[b-1]+=1

c=-1
s=0
while(True):
    c+=1
    if(c==N):
        break
    if S[c] == 1 :
        for i in range(N):
            if MAP[c][i] == 1 :
                MAP[c][i] = 0
                MAP[i][c] = 0
                S[c]-=1
                S[i]-=1
                s+=1
                c=-1
                break

print(s)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
 
 
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
 
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
 
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[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 C(x):
    U=UnionFind(n)
    for i in range(m):
        if i==x :
            continue
        U.unite(ab[i][0]-1, ab[i][1]-1)
    for i in range(n):
        for j in range(n):
            if not U.same(i, j):
                return False
    return True
ans=0
for y in range(m):
    if not C(y):
        ans+=1
print(ans)

Solution (Python):
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)

Solution (Python):
N, M = map(int,input().split())
E = []
for i in range(N+1):
    E.append([])
for _ in range(M):
    a, b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)

ORD = [0] * (N+1)
LOW = [0] * (N+1)
used = [False] * (N+1)
bridge = []

def dfs(idx, k, parent):
    global E,ORD,LOW,used,bridge
    used[idx] = True
    ORD[idx] = k
    LOW[idx] = k
    for to in E[idx]:
        if not used[to]:
            k = dfs(to, k+1, idx)
            LOW[idx] = min(LOW[idx], LOW[to])
            if ORD[idx] < LOW[to]:
                bridge.append(sorted([idx,to]))
        elif to != parent:
            LOW[idx] = min(LOW[idx], ORD[to])
    return k

dfs(1, 1, 0)
print(len(bridge))

Solution (Python):
n, m = map(int, input().split())
g = [[False] * n for _ in range(n)]
visited = [False] * n
a = []
b = []
ans = 0


def dfs(v):
    visited[v] = True
    for to in range(n):
        if not g[v][to]:
            continue
        if visited[to]:
            continue
        dfs(to)


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

for i in range(m):
    g[a[i]][b[i]] = False
    g[b[i]][a[i]] = False
    for j in range(n):
        visited[j] = False
    dfs(0)
    for j in range(n):
        if not visited[j]:
            ans += 1
            break
    g[a[i]][b[i]] = True
    g[b[i]][a[i]] = True

print(ans)

Solution (Python):
"""
解説PDFを見ながら実装
https://img.atcoder.jp/abc075/editorial.pdf
"""

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


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

    graph = []
    for _ in range(N):
        row = [False] * N
        graph.append(row)

    A = []
    B = []
    for _ in range(M):
        a, b = list(map(int, input().split()))
        a = a - 1
        b = b - 1
        A.append(a)
        B.append(b)
        graph[a][b] = True
        graph[b][a] = True
    

    ans = 0

    for i in range(M):
        
        graph[A[i]][B[i]] = False
        graph[B[i]][A[i]] = False

        visited = [False] * N

        
        dfs(0, graph, visited, N)

        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

    print(ans)

if __name__ == "__main__":
    main()

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

def bfs(n, t, v):
    for p in t[n]:
        if p not in visited:
            visited.add(p)
            bfs(p, t, v)

ans = 0
for i in range(M):
    t = {i:[] for i in range(1, N+1)}
    visited = set()
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j]
        t[a].append(b)
        t[b].append(a)
    bfs(1, t, visited)
    if len(visited) != N:
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
n,m=map(int,input().split())
es=[[[] for j in range(n)] for i in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for j in range(m):
        if i!=j:
            es[j][a].append(b)
            es[j][b].append(a)
sw = [[True for i in range(n)] for i in range(m)]
def dfs(v,k):
    sw[k][v] = False
    for i in es[k][v]:
        if sw[k][i]:
            dfs(i,k)
for i in range(m):
    dfs(0,i)
ans=0
for j in range(m):
    for i in range(n):
        if sw[j][i]:
            ans+=1
            break
print(ans)

Solution (Python):
import sys
import numpy as np

input = sys.stdin.readline
n,m = map(int, input().split())
ls = np.zeros([n,n])
for _ in range(m):
    a, b = map(int, input().split())
    if ls[a-1][b-1] == 0:
        ls[a-1][b-1] = 1
        ls[b-1][a-1] = 1

def dfs(a, visitedls):
    visitedls.append(a)
    for b in range(1,n+1):
        if ls[a-1][b-1] == 1 and b not in visitedls:
            dfs(b, visitedls)

def main():
    ans = 0
    for i in range(n):
        for j in range(n):
            if ls[i][j] == 1:
                ls[i][j] = 0
                visitedls = []
                dfs(i+1, visitedls)
                if len(visitedls) != n:
                    ans += 1
                ls[i][j] = 1
    print(int(ans/2))



if __name__ == "__main__":
    main()

Solution (Python):
import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,w = map(int,input().split())
l=[list(map(int,input().split())) for i in range(w)]
ans=0

for j in range(w):
    edge = [[] for i in range(n)]
    b=l[:j]+l[j+1:]
    for i in range(w-1):
        x,y = b[i][0],b[i][1]
        x-=1;y-=1
        z=1
        edge[x].append([z,y]) 
        edge[y].append([z,x]) 
    if float("inf") in dijkstra_heap(0):
            ans+=1
print(ans)

Solution (Python):
class UnionFind:

    def __init__(self, n):
        
        self.parent, self.depth = [-1] * n, [0] * n

    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 isSame(self, x, y):
        return self.find(x) == self.find(y)

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

        if self.depth[x] > self.depth[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.depth[x] == self.depth[y]:
                self.depth[y] += 1

    def numTree(self):
        return sum([1 for p in self.parent if p < 0])


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

ans = 0
for i in range(M):
    U = UnionFind(N)
    for a, b in E[:i] + E[i + 1:]:
        U.unite(a - 1, b - 1)
    if U.numTree() == 2:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
edge = [set() for i in range(N)]
l = []
for i in range(M):
  a, b = map(int, input().split())
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)
  l.append((a-1, b-1))

ans = M

for i in range(M):
  used = [False] * N
  a, b = l[i]
  edge[a].discard(b)
  edge[b].discard(a)

  stack = [0]
  while stack:
    prev = stack.pop()
    if used[prev]: continue

    used[prev] = True
    for to in edge[prev]:
      stack.append(to)
  
  if all(used): ans -= 1

  edge[a].add(b)
  edge[b].add(a)

print(ans)