Problem:


Score : 300 points

Problem Statement

You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges.

The i-th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i.  

An edge whose removal disconnects the graph is called a bridge.

Find the number of the edges that are bridges among the M edges.  

Notes

A self-loop is an edge i such that a_i=b_i (1 \leq i \leq M).

Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j (1 \leq i<j \leq M).

An undirected graph is said to be connected when there exists a path between every pair of vertices.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq min(N(N−1)⁄2,50)

1 \leq a_i<b_i \leq N

The given graph does not contain self-loops and double edges.

The given graph is connected.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

Output

Print the number of the edges that are bridges among the M edges.

Sample Input 1

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

Sample Output 1

4

The figure below shows the given graph:

The edges shown in red are bridges. There are four of them.

Sample Input 2

3 3
1 2
1 3
2 3

Sample Output 2

0

It is possible that there is no bridge.

Sample Input 3

6 5
1 2
2 3
3 4
4 5
5 6

Sample Output 3

5

It is possible that every edge is a bridge.



Sample input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7


Sample output:
4

Submission status: Accepted

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

edges = {}
node_count = 0
node_seen = set()
edge_list = []

def dfs(t_node, t_edge):
    global node_count, node_seen
    node_count += 1
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if t_node in t_edge and nextn in t_edge:
                pass
            else:
                dfs(nextn, t_edge)

def main():
    global edges, node_count, node_seen, edge_list
    n, m = map(int, input().split())
    all_nodes = set([i for i in range(1, n + 1)])
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
    # 処理
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(edge_list[itry][0], edge_list[itry])
        r += all_nodes != node_seen

    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n+1)]
edges = []
for _ in range(m):
    a,b = map(int,input().split())
    edges.append((a,b))
    g[a].append(b)
    g[b].append(a)
ans = 0
for a,b in edges:
    cnct = [False for _ in range(n+1)]
    cnct[a] = True
    que = deque([])
    for k in g[a]:
        if k!=b:
            que.append(k)
    while que:
        p = que.pop()
        if cnct[p] == True:
            continue
        else:
            cnct[p] = True
            for k in g[p]:
                que.append(k)
    if cnct[b] == False:
        ans += 1
print(ans)

Submission status: Accepted

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

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


def dfs(p, i, arrived):
    for n in G[p]:
        if arrived[n] is False and tuple(sorted((p, n))) != R[i]:
            arrived[n] = True
            dfs(n, i, arrived)


ans = 0
for i in range(M):
    arrived = [False]*N
    arrived[0] = True
    dfs(0, i, arrived)
    if not all(arrived):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[tuple(map(int,input().split())) for _ in range(M)]
ans=0
for i in range(M):
    tab=ab[:]
    tab.pop(i)
    r=[[] for _ in range(N)]
    for a,b in tab:
        r[a-1].append(b-1)
        r[b-1].append(a-1)
    l=[True]*N
    l[0]=False
    q=deque(r[0])
    while q:
        t=q.popleft()
        if l[t]:
            l[t]=False
            for j in r[t]:
                if r[j]:
                    q.append(j)
    ans+=any(l)
print(ans)

Submission status: Accepted

Solution code:
def BFS(graph):
    flags = [False]*n
    deque = collections.deque()
    deque.append(min(graph.keys()))
    while len(deque) > 0:
        item = deque.popleft()
        for i in graph[item]:
            if flags[i-1] == False:
                deque.append(i)
                flags[i-1] = True
    return all(flags)

import collections
def solve(n, m, ab_list):
    count = 0

    for i in range(m):
        graph = {}
        tmp_list = ab_list.copy()
        tmp_list.pop(i)
        for a, b in tmp_list:
            if a not in graph:
                graph[a] = []

            if b not in graph:
                graph[b] = []

            graph[a].append(b)
            graph[b].append(a)
        tmp = BFS(graph)
        if tmp == False:
            count += 1

    return count

if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    ab_list = [[int(j) for j in input().split()] for i in range(m)]
    print(solve(n, m, ab_list))

Submission status: Accepted

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

def is_connected(path, N):
    visited = [False] * N
    visited[0] = True
    que = deque([0])
    while que:
        pre = que.popleft()
        for next in range(N):
            if not visited[next] and path[pre][next]:
                visited[next] = True
                que.append(next)
    
    if sum(visited) == N:
        return True
    else:
        return False

def main():
    N, M = map(int, readline().rstrip().split())
    path = [[False] * N for _ in range(N)]
    edge = []
    for _ in range(M):
        a, b = map(int, readline().rstrip().split())
        edge.append((a-1, b-1))
        path[a-1][b-1] = True
        path[b-1][a-1] = True
    
    res = 0
    for a, b in edge:
        path[a][b] = False
        path[b][a] = False

        if not is_connected(path, N):
            res += 1

        path[a][b] = True
        path[b][a] = True

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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
        return True
    
def same(x,y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]
def func(a):
    return int(a)-1
n,m = map(int,input().split())
par = [-1]*n
ab = [list(map(func,input().split()))for i in range(m)]
ans = 0
for i in range(m):
    par = [-1]*n
    for j in range(m):
        if i != j:
            unite(ab[j][0],ab[j][1])
    for k in range(m):
        if not(same(ab[k][0],ab[k][1])):
            #print(k,ab[k][0]+1,ab[k][1]+1)
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
import copy
def main():
  global graph,vis,n
  n,m,*ab = map(int,open(0).read().split())
  ab = [(ab[i]-1,ab[i+1]-1) for i in range(0,len(ab),2)]
  master_graph = [[False]*n for _ in range(n)]
  for i,j in ab:
    master_graph[i][j] = True
    master_graph[j][i] = True
  ans = 0
  for i,j in ab:
    graph = copy.deepcopy(master_graph)
    graph[i][j] = False
    graph[j][i] = False
    vis = [False]*n
    dfs(0)
    if not(all(vis)):
      ans += 1
  print(ans)

def dfs(x):
  if not vis[x]:
    vis[x] = True
    for i in range(n):
      if graph[x][i]:
        dfs(i)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from collections import deque

def abc075_c():
    N, _ = map(int, readline().strip().split())
    edge_list = []  # 辺のリスト
    adj_mtx = np.zeros((N, N), dtype=int)  # 隣接行列(0-index)
    for ln in readlines():
        a, b = map(int, ln.strip().split())
        edge_list.append((a-1, b-1))
        adj_mtx[a-1, b-1] = adj_mtx[b-1, a-1] = 1

    def bfs(start: int, W: list):
        que = deque()  # 未訪問点
        dist = [-1] * len(W)  # 最短距離
        que.append(start)  # スタート地点で初期化
        dist[start] = 0  # スタート地点で初期化
        while que:
            here = que.popleft()  # 今いる点
            # 隣接点を処理
            for i, node in enumerate(W[here]):
                if node == 0: continue  # つながっていない
                if dist[i] != -1: continue  # 訪問済み
                dist[i] = dist[here] + 1  # 距離を更新
                que.append(i)  # 処理待ちに追加
        return dist

    ans = 0
    for a, b in edge_list:
        # 辺の1つを取り除く
        adj_mtx[a, b] = adj_mtx[b, a] = 0
        # bfsして未訪問点が存在するなら、取り除いた辺は橋である
        dist = bfs(0, adj_mtx.tolist())
        if -1 in dist: ans += 1
        # 取り除いた辺を元に戻す
        adj_mtx[a, b] = adj_mtx[b, a] = 1

    print(ans)

abc075_c()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

n, m = map(int, input().split())
ab = [input() for _ in range(m)]
# print(ab)
edge = [[] for _ in range(n)]  # 頂点n が辺を持つ頂点 かつ、へんの番号を入れる
for i in range(m):
    a, b = map(int, ab[i].split())
    a, b = a - 1, b - 1
    # print(a, b, edge)
    edge[a].append((b, i))
    edge[b].append((a, i))
ans = 0
for i in range(m):  # 全ての辺を消してみる
    visit = [0] * n
    visit[0] = 1
    stack = deque()
    stack.append(0)
    while stack:
        pos = stack.popleft()
        for j in edge[pos]:
            if j[1] == i or visit[j[0]]:  # その辺は使えない or すでに頂点に行っている
                pass
            else:
                stack.append(j[0])
                visit[j[0]] = 1
    # print(visit)
    if sum(visit) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*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.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

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

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

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N,M=map(int,readline().split())
    a=[0]*M
    b=[0]*M
    for i in range(M):
        a[i],b[i]=map(lambda x:int(x)-1,readline().split())
    
    res=0
    for i in range(M):
        t=UnionFind(N)
        for j in range(M):
            if j==i:
                pass
            else:
                t.union(a[j],b[j])
        if t.group_count()==2:
            res+=1
    
    print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

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

    def find(self, x):  # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # 要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

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

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

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

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

    def all_group_members(self):  # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

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


# 連結かどうかの判定->DFS, BFS, Dijkstra, UnionFindなどで解ける
N, M = map(int, input().split())
edge = []
for _ in range(M):
    u, v = map(int, input().split())
    edge.append((u-1, v-1))
cnt = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        a, b = edge[j]
        if i != j:
            uf.union(a, b)
    if uf.group_count() > 1:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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


# 連結かどうかの判定->DFS, BFS, Dijkstra, UnionFindなどで解ける
def dfs(s, check, a, b):
    for t in G[s]:
        if (s, t) == (a, b) or (s, t) == (b, a):
            continue
        if check[t]:
            continue
        check[t] = 1
        dfs(t, check, a, b)
    if 0 in check:
        return 1
    else:
        return 0

cnt = 0
for a, b in edge:
    check = [1] + [0] * (N-1)
    cnt += dfs(0, check, a, b)
print(cnt)

Submission status: Accepted

Solution code:
import sys

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N, M = map(int, sys.stdin.readline().rstrip().split())
edges = []
for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    edges.append((a-1, b-1))

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(edges):
        if i == j:
            continue
        uf.union(a, b)
    if uf.group_count() != 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]
    def get_group(self):
        a=0
        for i in range(len(self.par)):
          if self.find(i)==i:
            a+=1
        return a
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
ans=0
for i in range(M):
  uf=UnionFind(N)
  for j in range(M):
    if i==j:
      continue
    a,b=AB[j]
    uf.union(a-1,b-1)
  if uf.get_group()!=1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(10**5)

def dfs(u, visited, g, seq):
	visited[u] = True
	for v in g[u]:
		if visited[v] == True or not seq[u][v]:
			continue
		dfs(v, visited, g, seq)

def resolve():
	n, m = map(int, input().split())
	seq = [[True]*n for _ in range(n)]
	g = [[] for _ in range(n)]
	edges = []
	ans = 0
	for _ in range(m):
		a, b = map(int, input().split())
		edges.append([a-1, b-1])
	for i in range(m):
		g[edges[i][0]].append(edges[i][1])
		g[edges[i][1]].append(edges[i][0])

	for i in range(m):
		visited = [False]*n

		seq[edges[i][1]][edges[i][0]] = False
		seq[edges[i][0]][edges[i][1]] = False

		dfs(0, visited, g, seq)
		if len(visited) != visited.count(True):
			ans += 1
		seq[edges[i][1]][edges[i][0]] = True
		seq[edges[i][0]][edges[i][1]] = True
	print(ans)
resolve()

Submission status: Accepted

Solution code:
def dfs(u, visited, g):
	visited[u] = True
	for v in g[u]:
		if visited[v] == True:
			continue
		dfs(v, visited, g)

def resolve():
	n, m = map(int, input().split())

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

	for i in range(m):
		visited = [False]*n
		g = [[] for _ in range(n)]
		e = edges[:i] + edges[i+1:]
		for i in range(m-1):
			g[e[i][0]].append(e[i][1])
			g[e[i][1]].append(e[i][0])

		dfs(0, visited, g)
		if len(visited) != visited.count(True):
			ans += 1

	print(ans)
resolve()

Submission status: Accepted

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

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()}

Ms = [list(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
        a, b = Ms[j]
        uf.union(a-1, b-1)
    if uf.group_count()!=1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j):
        return self.find(i)==self.find(j)

    def get_parents(self):
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

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

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if (i==j):
            continue
        uf.unite(*adj[j])
    
    if len(set(uf.get_parents()))!=1: # 複数の集合にわかれているか確認
        ans += 1
print (ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j):
        return self.find(i)==self.find(j)

# if __name__=="__main__":
#     n, Q = map(int,input().split())
#     uf = UnionFind(n)
#     for q in range(Q):
#         cmd, i, j = map(int,input().split())
#         if cmd == 0:
#             uf.unite(i,j)
#         else:
#             print(int(uf.same(i,j)))
#     print (uf.sizes)
#     print (uf.parents)
#     print (uf.rank)

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

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if (i==j):
            continue
        uf.unite(*adj[j])
    
    for n in range(N):
        uf.find(n)
    #print (uf.parents)
    if len(set(uf.parents))!=1:
        ans += 1
    #break
print (ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
# n : 頂点の数, m : 辺の数
n, m = map(int, input().split())

# x : 各頂点に接続している頂点
x = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    x[a - 1].append([i, b - 1])
    x[b - 1].append([i, a - 1])

ans = 0

# 各辺についてそれを削除すると到達しない点があればansをインクリメント
for i in range(m):
    queue = deque([])
    visited = [0 for i in range(n)]
    queue.append(0)
    while queue:
        now = queue.popleft()
        if visited[now] == 1:
            continue
        visited[now] = 1
        for j in x[now]:
            if j[0] != i:
                queue.append(j[1]) 
        # if i == 4:
            # print(queue)
    if sum(visited) != n:
        ans += 1
    # if i == 4:
        # print(visited)
print(ans)

Submission status: Accepted

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

ab = [list(map(int,input().split())) for i in range(m)]
#逆順にしたもの追加
ab += [[b,a] for a,b in ab]

#辺id付きで、idがfrom,abi[from]=[to1,to2,...] のリスト
abi = [[] for _ in range(n+1)]
for i,(a,b) in enumerate(ab):
    abi[a].append(b)
    abi[b].append(a)


#再起のlimitを上げる
import sys
sys.setrecursionlimit(4100000)

from collections import deque



def dfs(i):
    visitted.append(i)
    flg = False
    for x in abi[i]:
        if x not in visitted and (i,x) != blocked and (x,i) != blocked:
            dfs(x)
            flg = True
    return len(visitted)==n

ret = 0
for i in range(m):
    blocked = (ab[i][0],ab[i][1])
    visitted = deque([])
    if not dfs(1):
        ret+=1

print(ret)

Submission status: Accepted

Solution code:
# pythonでスタック、キューを実現するためにdequeをimport
from collections import deque

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

# 辺集合EとグラフGの構築
G = [[] for _ in range(N)]
E = []
for _ in range(M):
    a, b = map(int, input().split())
    # 入力は1-indexedだがこれを扱いやすいように0-indexedに変更
    a -= 1
    b -= 1
    E.append((a, b))
    G[a].append(b)
    G[b].append(a)
# print(G)

# 橋を数えるための変数cntを用意
cnt = 0
for edge_to_remove in E:
    # 橋であるか判定したい辺を取り除いてみる
    i, j = edge_to_remove
    G[i].remove(j)
    G[j].remove(i)

    # 深さ優先探索
    seen = set()
    todo = deque()
    # 適当な頂点から深さ優先探索をスタート（ここでは頂点0をスタートに選んだ）
    todo.append(0)
    seen.add(0)
    while todo:
        here = todo.pop()
        for neighbor in G[here]:
            if neighbor not in seen:
                seen.add(neighbor)
                todo.append(neighbor)
    # print(seen)
    # もし訪問できていない頂点があれば連結でないというなので今着目している辺は橋であった！
    if len(seen) < N:
        cnt += 1

    # 次の辺について調べるために今取り除いた辺を再びGに戻しておく
    G[i].append(j)
    G[j].append(i)
print(cnt)

Submission status: Accepted

Solution code:
# pythonでスタック、キューを実現するためにdequeをimport
from collections import deque

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

# 辺集合EとグラフGの構築
G = [[] for _ in range(N)]
E = []
for _ in range(M):
    a, b = map(int, input().split())
    # 入力は1-indexedだがこれを扱いやすいように0-indexedに変更
    a -= 1
    b -= 1
    E.append((a, b))
    G[a].append(b)
    G[b].append(a)
# print(G)

# 橋を数えるための変数cntを用意
cnt = 0
for edge_to_remove in E:
    # 橋であるか判定したい辺を取り除いてみる
    i, j = edge_to_remove
    G[i].remove(j)
    G[j].remove(i)

    # 深さ優先探索
    seen = [False] * N
    todo = deque()
    # 適当な頂点から深さ優先探索をスタート（ここでは頂点0をスタートに選んだ）
    todo.append(0)
    seen[0] = True
    seen_nodes_num = 0
    while todo:
        here = todo.pop()
        seen_nodes_num += 1
        for neighbor in G[here]:
            if seen[neighbor] == False:
                seen[neighbor] = True
                todo.append(neighbor)
    # print(seen)
    # もし訪問できていない頂点があれば連結でないというなので今着目している辺は橋であった！
    if seen_nodes_num != N:
        cnt += 1

    # 次の辺について調べるために今取り除いた辺を再びGに戻しておく
    G[i].append(j)
    G[j].append(i)
print(cnt)

Submission status: Accepted

Solution code:
# pythonでスタック、キューを実現するためにdequeをimport
from collections import deque

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

# 辺集合EとグラフGの構築
G = [[] for _ in range(N)]
E = []
for _ in range(M):
    a, b = map(int, input().split())
    # 入力は1-indexedだがこれを扱いやすいように0-indexedに変更
    a -= 1
    b -= 1
    E.append((a, b))
    G[a].append(b)
    G[b].append(a)
# print(G)

# 橋を数えるための変数cntを用意
cnt = 0
for edge_to_remove in E:
    # 橋であるか判定したい辺を取り除いてみる
    i, j = edge_to_remove
    G[i].remove(j)
    G[j].remove(i)

    # 深さ優先探索
    seen = [False] * N
    todo = deque()
    # 適当な頂点から深さ優先探索をスタート（ここでは頂点0をスタートに選んだ）
    todo.append(0)
    seen[0] = True
    seen_nodes_num = 0
    while todo:
        here = todo.popleft()
        seen_nodes_num += 1
        for neighbor in G[here]:
            if seen[neighbor] == False:
                seen[neighbor] = True
                todo.append(neighbor)
    # print(seen)
    # もし訪問できていない頂点があれば連結でないというなので今着目している辺は橋であった！
    if seen_nodes_num != N:
        cnt += 1

    # 次の辺について調べるために今取り除いた辺を再びGに戻しておく
    G[i].append(j)
    G[j].append(i)
print(cnt)