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:
from collections import deque, defaultdict
import sys
sys.setrecursionlimit(2**20)
class LowLink:
    """
    与えられたグラフの関節点と橋を求める
    Attributes:
    size: グラフの頂点数
    pre: preorderでの訪問順
    low: ### 1. prenum[u]
        ### 2. GのBackEdge(u,v)が存在する場合は、prenum[v]
        ### 3. uの全ての子childに対してlowest[child]
    articulations<list>: 関節点のリスト
    bridges<list>: 橋のリスト

    """
    def __init__(self, v):
        self.size = len(v) + 1
        self.v = v
        self.pre = [None]*self.size
        self.low = [None]*self.size
        self.articulations = []
        self.bridges = []
        for x in range(self.size):
            if self.pre[x] is None:
                self.cnt = 0
                self.dfs(x, None)
    
    def dfs(self, x, prev):
        """
        DFSにより橋と関節点を求める
        x: 現在訪れているノード
        prev: ひとつ前のノード
        """
        self.pre[x] = self.low[x] = self.cnt # 初期化
        self.cnt += 1 # 
        is_articulation = False
        n = 0 # xから出ている子の個数
        for y in self.v[x]:
            if self.pre[y] is None: #yが未訪問なら
                n += 1 # xから出ている子の個数
                low_y = self.dfs(y, x) # 再帰呼び出し
                if low_y < self.low[x]:
                    # 最小値を更新できるなら
                    self.low[x] = low_y
                if self.pre[x] <= low_y:
                    if self.pre[x]: 
                        is_articulation = True
                    if self.pre[x] < low_y:
                        self.bridges.append(
                            (min(x,y), max(x,y))
                        )
            else:
                if y != prev and self.pre[y] < self.low[x]:
                    # yが以前訪れた物ではなくて、
                    # pre[y] < low[x]なら
                    self.low[x] = self.pre[y]
        
        if prev is None and n > 1:
            # prev is None == xが根 and
            # n > 1: 根xから子が2個以上出てるなら
            is_articulation = True
        
        if is_articulation:
            self.articulations.append(x)
        
        return self.low[x]

def solve():
    V, E = map(int, input().split())
    G = defaultdict(lambda: [])
    for _ in range(E):
        s, t= map(int, input().split())
        G[s].append(t)
        G[t].append(s)
    
    #initialize
    lowlink = LowLink(G)
    #bridges
    bridges = lowlink.bridges
    print(len(bridges))

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
N, M = map(int, input().split())
adj = [[0]*(N+1) for _ in range(N+1)] #1idx
edges = [tuple(map(int, input().split())) for _ in range(M)]
bridges = []
for e in edges:
    x,y=e
    adj[x][y] = 1
    adj[y][x] = 1

for bridge in edges:
    bx, by = bridge
    adj[bx][by] = 0
    adj[by][bx] = 0
    seen = [0]*(N+1)
    def dfs(s):
        seen[s] = 1
        for nx in range(1, N+1):
            if adj[s][nx]:
                if seen[nx]:
                    continue
                dfs(nx)
    dfs(1)
    is_ok = 1
    for i in range(1, N+1):
        if not seen[i]:
            is_ok = 0
            break
    if not is_ok:
        bridges.append(bridge)
    adj[bx][by] = 1
    adj[by][bx] = 1

print(len(bridges))

Submission status: Accepted

Solution code:
N, M = (int(x) for x in input().split())
edge = [tuple(int(x) for x in input().split()) for _ in range(M)]

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
INF = 100
tmpl_graph = [[INF if i != j else 0 for j in range(N)] for i in range(N)]

ans = 0
for E in edge:
    edgeWithoutE = edge.copy()
    edgeWithoutE.remove(E)
    graph = np.array(tmpl_graph)
    for x in edgeWithoutE:
        graph[x[0]-1,x[1]-1] = 1
        graph[x[1]-1,x[0]-1] = 1
    graph = floyd_warshall(graph,directed=False)
    if len(graph[graph == 100]) > 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind: #引数は頂点の数、1インデックス
    def __init__(self, n):
        self.parents = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.parents[x] == x:
            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 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 same_check(self, x, y):
        return self.find(x) == self.find(y)


if __name__ == "__main__":
    N, M = map(int, input().split())
    bridges = [tuple(map(int, input().split())) for _ in range(M)]

    count = 0
    for i in range(M):
        union_find = UnionFind(N)
        for j in range(M):
            if i == j:
                continue
            a, b = bridges[j]
            union_find.union(a, b)

        for j in range(1, N):
            if union_find.find(j) != union_find.find(j+1):
                count += 1
                break

    print(count)

Submission status: Accepted

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

for i in range(M):
    ab[i][0], ab[i][1] = map(int, input().split())
    to1[ab[i][0]-1].append(ab[i][1]-1)
    to1[ab[i][1]-1].append(ab[i][0]-1)

ans = 0

def DFS(n):
    global v
    if v[n] == 1:
        return
    v[n] = 1
    for i in to1[n]:
        DFS(i)

for i in range(M):
    v = [0] * N
    p = ab[i]
    p[0] -= 1
    p[1] -= 1
    to1[p[0]].remove(p[1])
    to1[p[1]].remove(p[0])
    DFS(0)
    if sum(v) != N:
        ans += 1
    to1[p[0]].append(p[1])
    to1[p[1]].append(p[0])

print(ans)

Submission status: Accepted

Solution code:
import sys

# https://ikatakos.com/pot/programming_algorithm/data_structure/union_find_tree
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def is_linked(self):
        if len(set([self._root(i) for i in range(len(self.table))])) <= 1:
            return True
        else:
            return False

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    ans = 0
    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if j == i:
                continue
            uf.union(*edges[j])
        if not uf.is_linked():
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

def main():
	N, M = [int(n) for n in input().split(" ")]
	edges = [[] for i in range(N)]
	# edges[i] : edges from vertex i 
	r = []
	for i in range(M):
		a, b = [int(x) for x in input().split(" ")]
		edges[a - 1].append(b - 1)
		edges[b - 1].append(a - 1)
		r.append([a - 1, b - 1])
	cnt = 0
	for i in range(len(r)):
		if not isConnected(edges, r[i]):
			cnt += 1
	print(cnt)

def isConnected(edges, remove_edge):
	n_v = len(edges)
	checked = [0] * n_v
	to_check = [0]
	e = copy.deepcopy(edges)
	e[remove_edge[0]].remove(remove_edge[1])
	e[remove_edge[1]].remove(remove_edge[0])
	while len(to_check) > 0:
		checking = to_check.pop(0)
		checked[checking] = 1
		for i in e[checking]:
			if checked[i] == 1:
				continue
			else:
				to_check.append(i)
	if n_v == sum(checked):
		return True
	else:
		return False


main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n
    def root(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def size(self, x):
        return -self.d[self.root(x)]
    def num_union(self):
        return self.u


import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
E = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(E):
        if i == j:
            continue
        uf.unite(a, b)
    if uf.num_union() != 1:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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


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

ans = 0
for i in range(M):
    #初期化
    #根なら-size,子なら親の頂点
    par = [-1]*N
    for j in range(M):
        if i==j:
            continue
        else:
            unite(ab[j][0]-1,ab[j][1]-1)
    
    if size(1)!=N:
        ans+=1

print(ans)

Submission status: Accepted

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

h = deque([])

for _ in range(m):
    l = list(map(int,input().split()))
    h.append(l)
count = 0

for i in range(m):
    if i != 0:
        h.append([a1,b1])
    a1,b1 = h.popleft()
    g = [[] for _ in range(number)]
    for a,b in h:

        g[a-1].append(b)
        g[b-1].append(a)

    q = deque([a1])
    pre = [0]*number
    pre[a1-1] = 1
    while q:
        now = q.popleft()

        for n in g[now-1]:

            if pre[n-1] == 0:
                q.append(n)
                pre[n-1] = 1
            else:
                continue
    
    if sum(pre) != number:
        count+=1

print(count)

Submission status: Accepted

Solution code:
import networkx as nx

n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_edges_from(zip(AB[::2], AB[1::2]))
print(len(list(nx.bridges(G))))

Submission status: Accepted

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

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        if x > y:
            x, y = y, x
        self._table[x] += self._table[y]
        self._table[y] = x
    
    def same(self, x, y):
        return self._root(x) == self._root(y)

    def count_members(self, x):
        return -self._table[self._root(x)]
    
    def count_groups(self):
        return len({self._root(i) for i in range(self._n)})
    
    def __str__(self):
        return str([self._root(i) for i in range(self._n)])
    
    def __repr__(self):           
        return repr([self._root(i) for i in range(self._n)])

n, m, *AB = map(int, open(0).read().split())
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(zip(AB[::2], AB[1::2])):
        if i == j:
            continue
        uf.unite(a-1, b-1)
    ans += uf.count_groups() != 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
vis = [0 for i in range(0 , 2000)]
lt = [0 for i in range(0 , 2000)]
dis = [0 for i in range(0 , 2000)]
adj = defaultdict(list)
time = 0
ans = 0
def dfs(u , p):
	global time , ans
	time = time+1
	lt[u]= dis[u]=time
	vis[u]=1
	for v in adj[u]:
		if v==p:
			continue
		if vis[v]==0:
			dfs(v , u)
			lt[u]=min(lt[u] , lt[v])# if back edge through child v
			if lt[v]>dis[u]:
				ans = ans+1
		else:
			lt[u]=min(lt[u] , dis[v])# if there is a back edge to a child v
def main():
	n , m = map(int , input().split())
	for i in range(0 , m):
		u, v= map(int , input().split())
		adj[u].append((v))
		adj[v].append((u))
	dfs(1, 0)
	print(ans)
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict
vis = [0 for i in range(0 , 2000)]
lt = [0 for i in range(0 , 2000)]
dis = [0 for i in range(0 , 2000)]
adj = defaultdict(list)
time = 0
ans = 0
def dfs(u , p):
	global time , ans
	time = time+1
	lt[u]= dis[u]=time
	vis[u]=1
	for v in adj[u]:
		if v==p:
			continue
		if vis[v]==0:
			dfs(v , u)
			lt[u]=min(lt[u] , lt[v])
			if lt[v]>dis[u]:
				ans = ans+1
		else:
			lt[u]=min(lt[u] , dis[v])
def main():
	n , m = map(int , input().split())
	for i in range(0 , m):
		u, v= map(int , input().split())
		adj[u].append((v))
		adj[v].append((u))
	dfs(1, 0)
	print(ans)
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def dfs(j):
  if j not in finish:
    finish.add(j)
    for k in L[j]:
      dfs(k)
N,M=MAP()
s=list()
L=[[] for _ in range(N)]
for i in range(M):
  a,b=MAP()
  a-=1
  b-=1
  L[a].append(b)
  L[b].append(a)
  s.append([a,b])
ans=0
for i in range(M):
  a,b=s[i]
  L[a].remove(b)
  L[b].remove(a)
  finish=set()
  dfs(a)
  if len(finish)!=N:
    ans+=1
  L[a].append(b)
  L[b].append(a)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append([i,v])
    graph[v].append([i,u])
    
cnt = 0
for i in range(m):
    d = deque()
    d.append(0)
    visited = [False]*n
    visited[0] = True
    while d:
        cf = d.pop()
        for ci, ct in graph[cf]:
            if ci == i:
                continue
            if not visited[ct]:
                d.append(ct)
                visited[ct] = True
    if False in visited:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():
    """
    parents
        各要素の親要素の番号を格納するリスト
        要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    find(x)
        要素xが属するグループの根を返す
    union(x, y)
        要素xが属するグループと要素yが属するグループとを併合する
    size(x)
        要素xが属するグループのサイズ（要素数）を返す
    same(x, y)
        要素x, yが同じグループに属するかどうかを返す
    members(x)
        要素xが属するグループに属する要素をリストで返す
        関連記事: Pythonリスト内包表記の使い方
    roots()
        すべての根の要素をリストで返す
    group_count()
        グループの数を返す
    all_group_members
        {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        関連記事: Pythonで辞書を作成するdict()と波括弧、辞書内包表記
    __str__()
        print()での表示用
        ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    """
    
    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())
ab=[tuple(map(int,input().split())) for _ in range(M)]
ans=0

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

Submission status: Accepted

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

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

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


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

count = 0
for i in range(M):
    uni = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uni.merge(A[j], B[j])
    # UnionFindの連結成分の個数を数える
    roots = [uni[x] for x in uni.root[1:]]
    counter = Counter(roots)
    if len(counter) > 1:
        count += 1

print(count)

Submission status: Accepted

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

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


for i in cnt:
  judge=False
  j=i[0]
  Q=[j]
  visited=[False]*n
  
  while Q:
      v=Q.pop(0)
      for k in lst[v]:
        if (v==i[0] and k==i[1]) or (v==i[1] and k==i[0]):
          continue
        if visited[k]==False:
              visited[k]=True
              Q.append(k)

  if visited[i[1]]==True:
      judge=True

  
  if judge:
    ans-=1


print(ans)

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

count = 0
for i in range(m):
    edges = [[]*n for _ in range(n)]
    for j in range(m):
        if j == i:
            continue
        edges[ab[j][0]-1].append(ab[j][1]-1)
        edges[ab[j][1]-1].append(ab[j][0]-1)
    #print(edges)
    d = deque([0])
    visited = [0]*n
    visited[0] = 1
    while d:
        p = d.pop()
        for child in edges[p]:
            if visited[child] == 1:
                continue
            visited[child] = 1
            d.append(child)
    if sum(visited) != n:
        count += 1
print(count)

Submission status: Accepted

Solution code:
class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        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 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[y]+=1

    def same(self,x,y):
        return self.find(x) == self.find(y)
      
n,m=map(int,input().split())
uf=union_find(n)
ans=0
s=[]
for _ in range(m):
  a=list(map(int,input().split()))
  s.append(a)
  uf.union(a[0],a[1])
  
  

for e in range(m):
  uf1=union_find(n)
  ch=0
  for d in range(m):
    if d!=e:
      uf1.union(s[d][0],s[d][1])
      
  for i in range(1,n):
    for j in range(i+1,n+1):
      if not uf1.same(i,j):
        ch+=1
  if ch>0:
    ans+=1

    
print(ans)

Submission status: Accepted

Solution code:
def FindParent(X):
    if Parent[X]==X:
        return X
    else:
        Parent[X] = FindParent(Parent[X])
        return Parent[X]

def CheckParent(X,Y):
    return FindParent(X)==FindParent(Y)

def UniteParent(X,Y):
    X = FindParent(X)
    Y = FindParent(Y)
    if X==Y:
        return 0
    if Rank[X]<Rank[Y]:
        Parent[X] = Y
    else:
        Parent[Y] = X
        if Rank[X]==Rank[Y]:
            Rank[X] += 1

import copy
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
    
Count = 0
for TM in range(0,M):
    ListCopy = copy.deepcopy(List)
    del ListCopy[TM]
    
    Parent = [I for I in range(N+1)]
    Rank = [0]*(N+1)
    for TTM in range(0,M-1):
        UniteParent(ListCopy[TTM][0],ListCopy[TTM][1])

    if not CheckParent(List[TM][0],List[TM][1]):
        Count += 1
print(Count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    edges.append((a, b))

parent = [i for i in range(N)]
height = [1] * N

def find(i):
    while i != parent[i]:
        i = parent[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    if height[i] >= height[j]:
        parent[j] = i
        height[i] = max(height[i], height[j] + 1)
    else:
        parent[i] = j
        height[j] = max(height[j], height[i] + 1)

bridges = 0
for cand in range(M):
    parent = [i for i in range(N)]
    height = [1] * N
    islands = N
    for i in range(M):
        if i == cand:
            continue
        a, b = edges[i]
        if find(a) == find(b):
            continue
        islands -= 1
        union(a, b)
    if islands > 1:
        bridges += 1
print(bridges)

Submission status: Accepted

Solution code:
def FindParent(X):
    if Parent[X]==X:
        return X
    else:
        Parent[X] = FindParent(Parent[X])
        return Parent[X]

def UniteParent(X,Y):
    X = FindParent(X)
    Y = FindParent(Y)
    if X==Y:
        return 0
    if Rank[X]<Rank[Y]:
        Parent[X] = Y
    else:
        Parent[Y] = X
        if Rank[X]==Rank[Y]:
            Rank[X] += 1

import copy
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
    
Count = 0
for TM in range(0,M):
    ListCopy = copy.deepcopy(List)
    del ListCopy[TM]
    
    Parent = [I for I in range(N+1)]
    Rank = [0]*(N+1)
    for TTM in range(0,M-1):
        UniteParent(ListCopy[TTM][0],ListCopy[TTM][1])
    for TN in range(1,N+1):
        FindParent(TN)
    if len(set(Parent[1:]))>1:
        Count += 1
print(Count)

Submission status: Accepted

Solution code:
from networkx import *
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
g = Graph(a)
print(len(tuple(bridges(g))))

Submission status: Accepted

Solution code:
from networkx import *
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
g = Graph(a)
ans = 0
for x in a:
  g.remove_edges_from([x])
  if not is_connected(g):
    ans += 1
  g.add_edges_from([x])
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[] for _ in range(N)]
H = []
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append([b,i]);G[b].append([a,i]) #iを辺のIDとして保存
  H.append([a,b])
ans = 0

def dfs(v,ID): #IDの辺を使えない
  visited.add(v)
  for u,idx in G[v]:
    if idx == ID or u in visited:
      continue
    dfs(u,ID)

for i in range(M):
  visited = set([])
  start = H[i][0]
  goal = H[i][1]
  dfs(start,i)
  if goal not in visited:
    ans +=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

N, M = map(int, input().split())
edge = []
bridge = 0
for _ in range(M):
  e = list(map(lambda x: int(x)-1, input().split()))
  edge.append(e)

for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if j == i:
      continue
    uf.unite(edge[j][0], edge[j][1])
  if uf.find_root(edge[i][0]) != uf.find_root(edge[i][1]):
    bridge += 1

print(bridge)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

N, M = map(int, input().split())
edge = []
bridge = 0
for _ in range(M):
  e = list(map(lambda x: int(x)-1, input().split()))
  edge.append(e)

for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if j == i:
      continue
    uf.unite(edge[j][0], edge[j][1])
  
  root = uf.find_root(0)
  for i in range(1, N):
    if root != uf.find_root(i):
      bridge += 1
      break

print(bridge)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
r=0
for m in range(M):
    c=[[] for i in range(N)]
    for i,(a,b) in enumerate(AB):
        if i!=m:
            c[a-1].append(b-1)
            c[b-1].append(a-1)
    q=[0]
    v=[1]+[0]*(N-1)
    while q:
        p=q.pop()
        for n in c[p]:
            if v[n]==0:
                v[n]=1
                q.append(n)
    if 0 in v:
        r+=1
print(r)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N + 1))
        self._rank = [0] * (self.N + 1)
        self._size = [1] * (self.N + 1)

    def find(self, x):
        if self._parent[x] != x:
            self._parent[x] = self.find(self._parent[x])
        return self._parent[x]

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

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

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


def main():
    N, M = map(int, input().split())
    a = [None] * M
    b = [None] * M
    for i in range(M):
        a[i], b[i] = map(int, input().split())

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def BFS(N,M,List):
    Edge = [[] for TN in range(N+1)]
    for TM in range(0,M):
        Edge[List[TM][0]].append(List[TM][1])
        Edge[List[TM][1]].append(List[TM][0])

    Distance = [-1]*(N+1)
    Distance[0] = 0
    Distance[1] = 0
    
    From = [0]*(N+1)
    From[1] = 1

    Deque = deque()
    Deque.append(1)
    while Deque:
        Now = Deque.popleft()
        for Con in Edge[Now]:
            if Distance[Con]==-1:
                Distance[Con] = Distance[Now]+1
                Deque.append(Con)
                From[Con] = Now

    return Distance[1:],From[1:]

import copy
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
Count = 0
for TM in range(0,M):
    ListCopy = copy.deepcopy(List)
    del ListCopy[TM]
    Distance,From = BFS(N,M-1,ListCopy)
    if -1 in Distance:
        Count += 1
print(Count)