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:
# 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
    while todo:
        # 深さ優先探索との実装上の違いはここでpopを使うかpopleftを使うかだけ
        # popならスタックなので深さ優先探索となりpopleftならキューなので幅優先探索となる
        here = todo.popleft()
        # print(here)
        for neighbor in G[here]:
            if seen[neighbor] == False:
                seen[neighbor] = True
                todo.append(neighbor)
    # print(seen)
    # もし訪問できていない頂点があれば連結でないというなので今着目している辺は橋であった！
    if False in seen:
        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
    while todo:
        here = todo.pop()
        for neighbor in G[here]:
            if seen[neighbor] == False:
                seen[neighbor] = True
                todo.append(neighbor)
    # print(seen)
    # もし訪問できていない頂点があれば連結でないというなので今着目している辺は橋であった！
    if False in seen:
        cnt += 1

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

Submission status: Accepted

Solution code:
from collections import deque


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

# 辺集合Eとグラフの構築
G = [[] for _ in range(N)]
E = []
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    E.append((a, b))
    G[a].append(b)
    G[b].append(a)
# print(G)

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()
    todo.append(0)
    seen[0] = True
    while todo:
        here = todo.pop()
        for neighbor in G[here]:
            if seen[neighbor] == False:
                seen[neighbor] = True
                todo.append(neighbor)
    # print(seen)
    if False in seen:
        cnt += 1
    
    G[i].append(j)
    G[j].append(i)
print(cnt)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

    # これ追加
    def count_group(self):
        return len({self.find(x) for x in range(n)})

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

cnt = 0
# 自分以外の道を全て繋いで一つのグループになるか（自分を繋がなくてもグループが一つにまとまるか）
# を調べる
for i in range(m):
    # UnionFindをm回生成する
    U = UnionFind(n)
    # 自分以外の道を全てunionしていく
    for j in range(m):
        if i == j:
            continue
        a, b = lista[j]
        U.union(a - 1, b - 1)
    # 繋ぎ終わったら全体でグループが１つにまとまっているか調べる
    if U.count_group() > 1:
        cnt += 1
print(cnt)

Submission status: Accepted

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

pairs = []
for _ in range(M):
    a, b = map(int, input().split())
    pairs.append([a, b])

Nodes = [{} for i in range(N)]
for pair in pairs:
    a, b = pair
    a -= 1
    b -= 1
    Nodes[a][b] = 1
    Nodes[b][a] = 1


def dfs(i):
    isFound[i] = True
    for neighbor in tmp_Nodes[i]:
        if isFound[neighbor] == False:
            dfs(neighbor)


count = 0
for skip in range(M):
    tmp_Nodes = copy.deepcopy(Nodes)
    a, b = pairs[skip]
    a -= 1
    b -= 1
    tmp_Nodes[a].pop(b)
    tmp_Nodes[b].pop(a)

    isFound = [False for _ in range(N)]
    dfs(0)
    #print(isFound)
    for v in isFound:
        if v == False:
            count += 1
            break

print(count)

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(g, v, visited):
    visited[v] = True

    for v2 in range(len(visited)):
        if not g[v][v2]:
            continue
        if visited[v2]:
            continue
        dfs(g, v2, visited)


def main():
    n, m = map(int, stdin.readline().split())
    ab = [list(map(int, stdin.readline().split())) for _ in range(m)]
    g = [[False] * n for _ in range(n)]
    for a, b in ab:
        g[a - 1][b - 1] = True
        g[b - 1][a - 1] = True

    ans = 0

    for i in range(m):
        visited = [False for _ in range(n)]
        a, b = ab[i]
        g[a - 1][b - 1] = False
        g[b - 1][a - 1] = False

        dfs(g, 0, visited)

        check = False
        for v in visited:
            if not v:
                check = True
        if check:
            ans += 1

        g[a - 1][b - 1] = True
        g[b - 1][a - 1] = True

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    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 check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        # rankの小さいものを大きいほうにくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self):
        return len({self.find(x) for x in range(1, n + 1)})

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

cnt = 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, b)

    if uf.count_group() > 1:cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

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[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, node in enumerate(nodelist):
            if j == i:
                continue
            uf.union(node[0], node[1])
        parent = []
        for k in range(N):
            parent.append(uf.find(k))
        if len(set(parent)) > 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        # 初期状態は全要素が根なので、親は自分自身
        self.par = [i for i in range(n+1)]
        # 集団の要素数(size)を格納する(初期は全て1)
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        # 根までたどったらその番号を返す
        if self.par[x] == x:
            return x
        # 根でないなら親の要素で再検索
        else:
            # 検索過程で親を書き換える(圧縮経路)
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    def unite(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # サイズを比較し、小さい方を大きい方に繋げる
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            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):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c
    

def main():
    N,M,*ab = map(int, read().split())

    E = []
    for a, b in zip(*[iter(ab)]*2):
        E.append((a, b))

    ans = 0
    for i in range(M):
        # i番目以外をつなぐ
        uf = UnionFind(N)
        for j, (a, b) in enumerate(E):
            if j == i:
                continue
            uf.unite(a, b)
        if uf.get_size(E[i][0]) + uf.get_size(E[i][1]) == N:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import copy

readline = sys.stdin.readline

def dfs(p, x):
    global graphtmp, check
    to = graphtmp[x]
    check[x] = 1
    for t in to:
        if p == t or check[t] == 1:
            continue
        dfs(x, t)

def main():
    global graphtmp, check
    N, M = map(int, readline().split())
    graph = [[] for _ in range(N)]
    nodelist = []
    for _ in range(M):
        a, b = map(int, readline().split())
        a -= 1; b-= 1
        nodelist.append([a, b])
        graph[a].append(b)
        graph[b].append(a)
    
    ans = 0
    for nodetmp in nodelist:
        check = [0]*N
        graphtmp = copy.deepcopy(graph)
        graphtmp[nodetmp[0]].remove(nodetmp[1])
        graphtmp[nodetmp[1]].remove(nodetmp[0])
        dfs(-1, 0)
        if 0 in check:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
from collections import deque
A = [[] for i in range(N)]
line_list = []
ans = 0
for i in range(M):
    B,C = map(int,input().split())
    B -=1
    C -=1
    A[B].append(C)
    A[C].append(B)
    line_list.append([B,C])
for i in range(M):#一辺ずつ
    B = 0
    C = line_list[i]
    start = C[0]
    end = C[1]
    que = deque(A[start])
    que.remove(end)
    after = deque([start])
    while que != deque([]):
        now = que.popleft()
        after.append(now)
        for j in A[now]:
            if j in after:
                continue
            if j in que:
                continue
            que.appendleft(j)
        if end in que:
            B = 1
            break
    if B != 1:
        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 deque
inf=10**9


def BFS(s,num):
    color=["white" for _ in range(n+1)]
    D=[inf for _ in range(n+1)]
    M=[[] for _ in range(n+1)]

    for i in range(m):
        if i==num:continue
        a,b=AB[i]
        M[a].append(b)
        M[b].append(a)

    D[s]=0
    color[s]="gray"

    queue=deque([s])
    while len(queue)>0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                D[i]=D[u]+1
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return True if inf in D[1:] else False


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

cnt=0
for i in range(m):
    cnt +=BFS(1,i)
print(cnt)

Submission status: Accepted

Solution code:
class UnionFindVerSize:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x]==xのときそのノードは根 1からn
        self.par = [i for i in range(n + 1)]
        # 木のサイズを格納
        self.size = [1] * (n + 1)

    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 is_same(self, x, y):
        # 根が同じならTrue
        return self.find(x) == self.find(y)

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

        # 木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[x] += self.size[y]
        else:
            self.par[y] = x
            self.size[y] += self.size[x]

    def get_size(self, x):
        return self.size(self.find(x))

    def get_group_num(self):
        ans = 0
        for i in range(1, len(self.par)):
            if self.find(i) == i:
                ans += 1
        return ans

N, M = map(int, input().split())
query = []
for i in range(M):
    query.append(list(map(int, input().split())))

ans = 0
for ignore in range(0, M):
    union = UnionFindVerSize(N)
    for i, q in enumerate(query):
        if i == ignore:
            continue
        union.unite(q[0], q[1])

    if union.get_group_num() >= 2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys


# import math
# import bisect

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize
# MOD = 10 ** 9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

# ===CODE===
def main():
    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,input().split())

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

    ans = 0
    for i in range(m):
        que = UnionFind(n)
        for j in range(m):
            if i!=j:
                que.union(d[j][0], d[j][1])

        if que.group_count() != 1:
            ans+=1

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

for a,b in ab:
  g[a-1].append(b-1)
  g[b-1].append(a-1)

def bfs(i,j):# iからjへのルートの数が2本以上あるかどうか。
  seen=[[-1]for _ in range(n)]
  seen[i]=[]
  todo=deque([[i]])
  c=0
  while len(todo)>0:
    d=todo.pop()
    l=g[d[-1]]
    for li in l:
      if li in d:
        continue
      if li==j:
        c+=1
        if c>1:
          return True
        continue
      e=d.copy()
      e.append(li)
      todo.append(e)
  return False

ans=0
for a,b in ab:
  ans+= 0 if bfs(a-1,b-1) else 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　par[x]==xのときそのノードは根 1からn
        self.par = [i for i in range(n+1)]
        #木の高さを格納
        self.rank = [0] * (n+1)

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        #木の高さを比較し、低いほうから高いほうへつなぐ
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

N, M = map(int, input().split())
query = []
for i in range(M):
    query.append(list(map(int, input().split())))

ans = 0
for ignore in range(0, M):
    union = UnionFind(N)
    for i, q in enumerate(query):
        if i == ignore:
            a, b = q[0], q[1]
            continue
        union.union(q[0], q[1])

    if not union.same_check(a, b):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True

class UnionFind(object):
    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()),


def main():
    N, M = MI()
    a = [0] * M
    b = [0] * M
    ans = 0

    for i in range(M):
        _a, _b = MI()
        a[i], b[i] = _a - 1, _b - 1

    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if i == j:
                continue
            uf.union(a[j], b[j])
        if len(uf.roots()) != 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edges=[list(map(int,input().split())) for i in range(m)]
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
ans=0
for i in range(m):
    f=UnionFind(n,1)
    for j in range(m):
        if j!=i:f.unite(*edges[j])
    if f.group_count()==2:ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())

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

class UnionFind():
    def __init__(self, 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 False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

ans = 0
for i in range(M):
        uf = UnionFind(N)
        for j, (a, b) in enumerate(V):
            if i != j:
                uf.union(a-1, b-1)
        if not uf.same(V[i][0]-1, V[i][1]-1):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())

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

class UnionFind():
    def __init__(self, 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 False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

ans = 0
for i in range(N):
    for j in range(i+1, N):
        uf = UnionFind(N)
        for a, b in V:
            if a-1 == i and b-1 ==j:
                continue
            uf.union(a-1, b-1)
        if not uf.same(i, j):
            ans += 1
print(ans)

Submission status: Accepted

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x
def is_same(x,y):
  return get_par(x) == get_par(y)

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

answer=0
for i in range(M):
  par_list = list(range(N+1))
  for j in range(M):
    if i==j:
      continue
    a,b=ablist[j]
    merge(a,b)

  comp_set=set()
  for i in range(1,N+1):
    comp_set.add(get_par(i))
  
  if len(comp_set)>1:
    answer+=1
  
print(answer)

Submission status: Accepted

Solution code:
import bisect

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

# UnionFind
class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

        if x == y:
            return
        else:
            if self.rank[x] <self.rank[y]:
                self.par[y] += self.par[x] # 負+負でsize管理 
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]: # 負+負でsize管理 
                    self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.par[self.root(x)]

Tree = UnionFind(N)
ans = 0
for i in range(1,N+1):
    for j in range(len(bridge[i])):
        erase_a = i
        erase_b = bridge[i][j]
        del bridge[i][j]

        for k in range(1,N+1):
            for l in range(len(bridge[k])):
                Tree.union(k-1,bridge[k][l]-1)
        
        if not Tree.is_same(erase_a-1,erase_b-1):
            ans += 1

        bisect.insort_left(bridge[erase_a],erase_b)

        Tree.__init__(N)

print(ans)

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def enumerate_bridges(graph):
    """
    橋を列挙する
    http://nupioca.hatenadiary.jp/entry/2013/11/03/200006
    :param list of (list of int) graph:
    """
    N = len(graph)
    ret_bridges = []
    pres = [-1] * N
    lows = [-1] * N
    order = -1
    for v in range(N):
        if pres[v] >= 0:
            continue
        edges = [(None, v, True)]
        while edges:
            v, u, forward = edges.pop()
            if forward:
                if pres[u] >= 0:
                    # もう来たことがある
                    lows[v] = min(lows[v], lows[u])
                    continue
                edges.append((v, u, False))
                parent, v = v, u
                order += 1
                pres[v] = lows[v] = order
                for u in graph[v]:
                    if u == parent:
                        continue
                    edges.append((v, u, True))
            else:
                if v is None:
                    continue
                if lows[u] == pres[u]:
                    ret_bridges.append((v, u))
                lows[v] = min(lows[v], lows[u])
    return ret_bridges


N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
bridges = enumerate_bridges(graph)
print(len(bridges))

Submission status: Accepted

Solution code:
from collections import defaultdict


def dfs(i, used, dic, ng):
    for n in dic[i]:
        if n not in used and (i, n) != ng and (n, i) != ng:
            used.add(n)
            dfs(n, used, dic, ng)


N, M = map(int, input().split())
dic = defaultdict(list)
lst = []
for _ in range(M):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)
    lst.append((a, b))

ret = 0
for a, b in lst:
    used = set()
    dfs(1, used, dic, (a, b))
    if len(used) != N:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
from collections import  deque

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

def dfs(st,check):
    check[st]=1
    for th in graph[st]:
        if check[th]==0 :
           dfs(th,check)

ans=0
for i in range(m):
    graph[count[i][0]].remove(count[i][1])
    graph[count[i][1]].remove(count[i][0])
    check = [0 for k in range(n)]
    dfs(0,check)
    if 0 in check:
        ans+=1
    graph[count[i][0]].append(count[i][1])
    graph[count[i][1]].append(count[i][0])

print(ans)