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:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
# C - Bridge
import copy
import itertools

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

all_edge_list = sorted(edge_list, key=lambda x: (x[0], x[1]))
all_node_list = list(set(list(itertools.chain.from_iterable(edge_list))))

bridge_list = []

for removed_edge in all_edge_list:  # 50
    r_a, r_b = removed_edge[0], removed_edge[1]

    # 当該エッジを除去した後のエッジリスト
    w_edge_list = copy.copy(all_edge_list)
    w_edge_list.remove((r_a, r_b))

    # 最初のエッジ
    a, b = w_edge_list[0]
    done_node_list = []
    done_node_list.append(a)
    done_node_list.append(b)

    done_edge_list = []
    done_edge_list.append((a, b))

    while True:
        # 探索済ノードから伸びているエッジを探す
        connected_edges = [edge for edge in w_edge_list if edge[0] in done_node_list or edge[1] in done_node_list]
        new_edges = set(connected_edges) - set(done_edge_list)
        for edge in new_edges:
            # 新しく見つかったエッジ
            done_edge_list.append(edge)
            done_node_list.append(edge[0])
            done_node_list.append(edge[1])
            done_node_list = list(set(done_node_list))
        if not new_edges:
            break

    if len(done_node_list) != len(all_node_list):
        # 全てのノードを探索し尽くしていない
        bridge_list.append((r_a, r_b))

ans = len(bridge_list)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, 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 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())
edges = [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:
            uf.union(edges[j][0]-1, edges[j][1]-1)
    c = 0
    for j in range(n):
        if j == uf.find(j):
            c += 1
    if c > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def dfs(v):
    visited[v] = True
    for v2 in range(n):
        if G[v][v2]==1 and visited[v2]==False:
            dfs(v2)
    

n, m = map(int, input().split())
a = [0]*m
b = [0]*m
G = [[0]*n for _ in range(n)]
visited = [False]*n

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

cnt = 0
for i in range(m):
    G[a[i]][b[i]] = G[b[i]][a[i]] = 0
    for j in range(n):
        visited[j] = False
    
    dfs(0)

    if False in visited:
        cnt += 1

    G[a[i]][b[i]] = G[b[i]][a[i]] = 1

print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return


n, m = map(int, input().split())
edges = [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:
            uf.union(edges[j][0]-1, edges[j][1]-1)
    c = 0
    for j in range(n):
        if j == uf.find(j):
            c += 1
    if c > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    n,m= map(int, sys.stdin.readline().split())

    visited = [False for i in range(n)]
    matrix = [[False for i in range(n)] for j in range(n)]

    a =[]
    b = []

    #dfsで連結判定
    def dfs(v):
        visited[v] = True
        for v2 in range(n): #頂点v2：vに隣接かつ未訪問の頂点
            if matrix[v][v2] == False:#頂点に隣接
                continue
            if visited[v2] == True:#未訪問
                continue
            dfs(v2) #

    #隣接行列
    for i in range(m):
        _a,_b = map(int,input().split())
        a.append(_a -1)
        b.append(_b -1)
        matrix[a[i]][b[i]] = True
        matrix[b[i]][a[i]] = True
        # a,b = map(int, input().split())
        # matrix[a-1][b-1] = matrix[b-1][a-1] = True
        # print(matrix)
        # print(a[i])
        # print(b)

    #グラフから辺を取り除いて連結するかはんてい
    ans = 0
    for i in range(m):#辺を一個ずつ取り除いていく
        matrix[a[i]][b[i]] = False#辺を取り除く
        matrix[b[i]][a[i]] = False
        # matrix[i][i]=False

        visited = [False for i in range(n)]#すべての辺を未訪問にする。
        # print(visited)
        dfs(0)#頂点を訪問していく操作を実行。再帰で辺をvisitedを更新。
        # print("after:",visited)

        bridge = False#橋判定。一個でも未訪問に
        for j in range(n):
            if(visited[j] == False):#すべての頂点が訪問済みになってれば連結、そうでなければ非連結
                bridge=True#一個でも訪問できなければ、その辺は橋
        # print(visited)
        if(bridge):
            ans +=1
        matrix[a[i]][b[i]] = matrix[b[i]][a[i]] = True #辺を戻す
        # matrix[i][i] = True
    print(ans)

Submission status: Accepted

Solution code:
import collections 
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,m = inpl()
t = []
cnt = [0] * (n+1)
ans = 0
for i in range(m):
    a,b = inpl()
    t.append([a,b])
    cnt[a] += 1
    cnt[b] += 1
# print(cnt)
while m:
    flag = False
    for i in range(1,n+1):
        if cnt[i] == 1:
            flag = True
            cnt[i] = 0
            ans += 1
            for j in t:
                if j[0] == i:
                    cnt[j[1]] -= 1
                    t.remove(j)
                elif j[1] == i:
                    cnt[j[0]] -= 1
                    t.remove(j)
            break
    if flag == False:
        break
    m -= 1
        # print(i,cnt)
print(ans)

Submission status: Accepted

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

def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]

def is_same(a,b):
    return root(a) == root(b)

def unite(a , b):
    ra = root(a)
    rb = root(b)
    if ra == rb:
        return
    parent[ra] = rb

ans = 0
for i in range(M):
    parent = [k for k in range(N)]
    for j , e in enumerate(edge):
        if j == i:
            continue
        a , b = e
        unite(a , b)
    a , b = edge[i]
    if not is_same(a , b):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
n, m = map(int, input().split(' '))
db = [[] for _ in range(n)]
a = []
b = []
for i in range(m):
    a_ ,b_ = map(int, input().split(' '))
    db[a_-1].append(b_-1)
    db[b_-1].append(a_-1)
    a.append(a_-1)
    b.append(b_-1)

def dfs(num):
    if checker[num] == 1:
        return 0
    checker[num] = 1
    for k in db_1[num]:
        dfs(k)
    return 0

counter = 0
for i in range(m):
    checker = [0 for _ in range(n)]
    db_1 = copy.deepcopy(db)
    db_1[a[i]].remove(b[i])
    db_1[b[i]].remove(a[i])
    dfs(a[i])
    if all(checker[s] == 1 for s in range(len(checker))):
        continue
    else:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
	x,y=map(int,input().split())
	a.append([x,y])
ans=0
for i in range(m):
	b=[a[i][0]]
	for j in range(n):
		for k in range(m):
			if k!=i and a[k][0] in b:
				b.append(a[k][1])
			elif k!=i and a[k][1] in b:
				b.append(a[k][0])
	if a[i][1] not in b:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
ab = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    a, b = ab[i][0] - 1, ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

def f(now):
    vi[now] = True
    for to in edge[now]:
        if (now == a and to == b) or (now == b and to == a):
            pass
        else:
            if vi[to] != True:
                f(to)

ans = 0
for s in ab:
    a = s[0] - 1
    b = s[1] - 1
    vi = [False] * N
    f(0)
    for v in vi:
        if not v:
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
import copy

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)

n,m = ips()
a = []
s = 0
for i in range(m):
    x,y = ips()
    a.append([x,y])
connection = [[] for i in range(n+1)]
for i in range(m):
    [x,y] = a[i]
    connection[x].append(y)
    connection[y].append(x)
for loop in range(50):
    for i in range(1,n+1):
        if len(connection[i]) == 1:
            temp = connection[i][0]
            d = connection[temp].index(i)
            connection[temp].pop(d)
            s+=1
            connection[i].pop(0)
print(s)

Submission status: Accepted

Solution code:
import copy

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)

n,m = ips()
a = []
s = 0
for i in range(m):
    x,y = ips()
    a.append([x,y])
connection = [[] for i in range(n+1)]
for i in range(m):
    [x,y] = a[i]
    connection[x].append(y)
    connection[y].append(x)
for loop in range(100):
    for i in range(1,n+1):
        if len(connection[i]) == 1:
            temp = connection[i][0]
            d = connection[temp].index(i)
            connection[temp].pop(d)
            s+=1
            connection[i].pop(0)
print(s)

Submission status: Accepted

Solution code:
def dfs(num):
  global visited
  for next_num in edge[num]:
    if visited[next_num]:
      continue
    if has_edge[num][next_num]:
      visited[next_num]=1
      dfs(next_num)
      
N,M = map(int,input().split())
ab = []
edge = [[] for x in range(N+1)]
has_edge = [[0 for x in range(N+1)] for x in range(N+1)]
for i in range(M):
  a,b = map(int,input().split())
  ab.append([a,b])
  edge[a].append(b)
  edge[b].append(a)
  has_edge[a][b] = 1
  has_edge[b][a] = 1
  
count = 0
for a,b in ab:
  visited = [0 for x in range(N+1)]
  visited[1] = 1
  has_edge[a][b] = 0
  has_edge[b][a] = 0
  dfs(1)
  if sum(visited) != N:
    count += 1
  has_edge[a][b] = 1
  has_edge[b][a] = 1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

def solve(graph, m, brg):
  ans = 0
  for i in range(m):
    if len(graph[i]) == 1 and set(sorted([graph[i][0], i])) not in brg:
      graph[graph[i][0]].remove(i)
      brg.append(set(sorted([graph[i][0], i])))
      ans += 1
  return ans, graph

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

brg = []
ans = 0
result = -1
while result != 0:
  result, graph = solve(graph, m, brg)
  ans += result
print(ans)

Submission status: Accepted

Solution code:


import sys
sys.setrecursionlimit(500000)

def dfs(i):
    global visited,neighbor
    visited[i] = 1
    for j in [k for k in range(N) if neighbor[i][k]==1]:
        if visited[j] == 1:
            continue
        dfs(j)


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

neighbor = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    neighbor[ab[i][0]][ab[i][1]] = 1
    neighbor[ab[i][1]][ab[i][0]] = 1
for i in range(M):
    neighbor[ab[i][0]][ab[i][1]] = 0
    neighbor[ab[i][1]][ab[i][0]] = 0
    visited = [0 for i in range(N)]
    dfs(0)
    neighbor[ab[i][0]][ab[i][1]] = 1
    neighbor[ab[i][1]][ab[i][0]] = 1
    if sum(visited) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        """
        ノード数nの配列を作る
        親の番号を格納する
        -> 自分が根だった場合は、-(その集合のサイズ)とする
        作るときはparentの値を全て-1にする
        こうすると全てバラバラになる
        """
        self.parent = [-1 for _ in range(n)]
 
    def root(self, x):
        """
        要素xの根の番号を返す
        """
        if self.parent[x] < 0:
            # 自分が根
            return x
        # 要素xの親を要素xの根に変えておく(付け替える)
        # 次の呼び出しが早くなる
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]
 
    def size(self, x):
        """
        要素xの所属するグループの頂点数を調べる
        根のparentにサイズが格納されている
        """
        return -self.parent[self.root(x)]
 
    def merge(self, x, y):
        """
        xとyを結合する
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
 
        #大きい方(x)に小さい方(y)をくっつけたい
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
    
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

N,M = map(int,input().split())
ab = []
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    ab.append([a,b])

for i in range(M):
    UF = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        UF.merge(ab[j][0]-1,ab[j][1]-1)
    if UF.size(0) == N:
        continue
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
(n, m) = map(int, input().split())
a = []
b = []
graph = [[False for _ in range(n)] for _ in range(n)]
for _ in range(m):
    (a_i, b_i) = map(int, input().split())
    a_i -= 1
    b_i -= 1
    graph[a_i][b_i] = True
    graph[b_i][a_i] = True
    a.append(a_i)
    b.append(b_i)


def dfs(v):
    visit[v] = True
    for i in range(n):
        if not graph[v][i]:
            continue
        if visit[i]:
            continue
        dfs(i)


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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)

def dfs(num):
    global visited, edge, has_edge
    for next_num in edge[num]:
        if visited[next_num]:
            continue
        if has_edge[num][next_num]:
            visited[next_num] = 1
            dfs(next_num)


n, m = map(int, input().split())
edge = [[] for _ in range(n+1)]
has_edge = [[0 for _ in range(n+1)] for _ in range(n+1)]
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append([a, b])
    edge[a].append(b)
    edge[b].append(a)
    has_edge[a][b] = 1
    has_edge[b][a] = 1

count = 0
for a, b in ab:
    visited = [0 for _ in range(n+1)]
    visited[1] = 1
    has_edge[a][b] = 0
    has_edge[b][a] = 0
    dfs(1)
    if sum(visited) != n:
        count += 1
    has_edge[a][b] = 1
    has_edge[b][a] = 1
print(count)

Submission status: Accepted

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

limit = 60

vis = [False]*(n+2)
graph = [[False for i in range(n+2)] for j in range(n+2)]

def dfs(x):
    vis[x] = True
    for i in range(1,n+1):
        if graph[x][i] == False:
            continue
        if vis[i] == True:
            continue
        #print(i)
        dfs(i)

for i in range(m):
    graph[ab[i][0]][ab[i][1]] = True
    graph[ab[i][1]][ab[i][0]] = True

bridge = 0

ans = 0

for i in range(m):
    vis = [False]*(n+2)
    graph[ab[i][0]][ab[i][1]] = False
    graph[ab[i][1]][ab[i][0]] = False
    
    dfs(1)
    #print(vis)
    #exit()
    
    bridge = False
    for j in range(1,n+1):
        if vis[j] == False:
            bridge = True
    if bridge:
        ans += 1
    
    graph[ab[i][0]][ab[i][1]] = True
    graph[ab[i][1]][ab[i][0]] = True

print(ans)

Submission status: Accepted

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

count=0
for i in range(m):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    x[i]=[u,v]
memo=[False for i in range(n)]
memo[0]=True


def dfs(now,prev):
    for next in g[now]:        
        if next!=prev:
            if memo[next]==True:
                continue
            else:
                memo[next]=True
                dfs(next,now)


for i in range(m):
    g[x[i][0]].remove(x[i][1])
    g[x[i][1]].remove(x[i][0])
    dfs(0,0)
    if memo.count(False)>=1:
        count+=1
    g[x[i][0]].append(x[i][1])
    g[x[i][1]].append(x[i][0])
    memo=[False for i in range(n)]
    memo[0]=True
    
print(count)

Submission status: Accepted

Solution code:
 

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

count=0
for i in range(m):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    x[i]=[u,v]
memo=[False for i in range(n)]
memo[0]=True

def dfs(now,prev):
    for next in g[now]:
        
        if next!=prev:
            if memo[next]==True:
                continue
            else:
                memo[next]=True
                dfs(next,now)


for i in range(m):
    g[x[i][0]].remove(x[i][1])
    g[x[i][1]].remove(x[i][0])
    dfs(0,0)
    if memo.count(False)>=1:
        count+=1
    g[x[i][0]].append(x[i][1])
    g[x[i][1]].append(x[i][0])
    memo=[False for i in range(n)]
    memo[0]=True
print(count)

Submission status: Accepted

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

def get_edges_include_node(i, Edges): # 頂点 i を含む辺のリストを返す
    es = []
    for e in Edges:
        if i in e:
            es.append(e)
    return es

def dfs(i, e0, goal, Edges): # 頂点 i から頂点 j にたどり着けるかどうか
    if e0 in Edges:
        Edges.remove(e0)
    for e1 in get_edges_include_node(i, Edges):
        if goal in e1:
            return True
        else:
            ni = e1[1] if e1[0] == i else e1[0]
            if dfs(ni, e1, goal, Edges):
                return True                
    return False
def main():

    N,M = map(int, input().split())
    Edges = []
    for _ in range(M):
        a,b = map(int, input().split())
        Edges.append((a,b))
    ans = 0
    for e in Edges:
        tmp = []
        for e2 in Edges:
            tmp.append((e2[0], e2[1]))
        if not dfs(e[0], e, e[1], tmp):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(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
            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 same_check(self, x, y):
        return self.find(x) == self.find(y)

bridge = 0

for i in range(m):
    ins = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        if not ins.same_check(ab[j][0],ab[j][1]):
            ins.union(ab[j][0],ab[j][1])
        
    #print(ins.size[1],ins.size[ins.find(2)])
    if ins.size[ins.find(ab[0][0])] != n:
        bridge += 1
        
print(bridge)

Submission status: Accepted

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

def dfs(n) :
    queue = [0]
    visited = [False] * N
    visited[0] = True
    counter = 1
    while queue :
        cur = queue.pop()
        for nex, i in v[cur] :
            if i == n : 
                continue
            if not visited[nex] :
                counter += 1
                queue.append(nex)
                visited[nex] = True
    
    return counter != N

ret = 0
for i in range(M) :
    if dfs(i) :
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
h=[list(map(int, input().split())) for i in range(M)]
a=0
def s(n,m,l):
    for j in range(n,m):
        if l[h[j][0]-1] or l[h[j][1]-1]:
            l[h[j][0]-1],l[h[j][1]-1]=1,1
    return(l)
for i in range(M):
    l=[1]+[0]*(N-1)
    for _ in range(N-1):
        l=s(0,i,l)
        l=s(i+1,M,l)
    if 0 in l:
        a+=1
print(a)

Submission status: Accepted

Solution code:
import collections
def main():
    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        a, b = [int(c) for c in input().split()]
        graph[a].append(b)
        graph[b].append(a)

    count = 0
    for a in graph:
        for b in graph[a]:
            if a < b:
                start, goal = a, b
                cur = [start]
                visited = set([start])
                isFound = False
                while cur and not isFound:
                    temp = []
                    for c in cur:
                        for d in graph[c]:
                            if [c, d] != [a, b] and d not in visited:
                                if d == goal:
                                    isFound = True
                                    break
                                visited.add(d)
                                temp.append(d)
                        if isFound:
                            break
                        cur = temp
                if not isFound:
                    count += 1
    return count

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

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

inf=10**9
n, m=map(int,input().split())
g1=np.ones((n,n),dtype=int) * inf

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

ans=0
for a,b in bridge:
    graph=np.copy(g1)
    graph[a][b]=inf
    graph[b][a]=inf
    graph=floyd_warshall(graph)
    if inf in graph:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
N, M = map(int, input().split())
D = defaultdict(list)
Edge = []
for i in range(M):
  A, B = map(int, input().split())
  D[A-1].append(B-1)
  D[B-1].append(A-1)
  Edge.append((A-1, B-1))
def dfs(n, vstd, i):
  vstd.add(n)
  for a in D[n]:
    if a not in vstd and (a, n) != i and (n,a) != i:
      dfs(a, vstd, i)
  return len(vstd)

cnt = 0
for i in Edge:
  if dfs(0, set(), i) < N:
    cnt += 1
print (cnt)

Submission status: Accepted

Solution code:
# ABC075C - Bridge
# find the number of bridges in a given undirected connected graph
# bridge := an edge whose removal disconnects a graph
import sys
from copy import deepcopy

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int) -> None:
    seen[v] = 1  # make vertex v searched
    for u in g[v]:
        if not seen[u]:
            dfs(u)


def main():  # O(M(N + M))
    global g, seen
    N, M = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  # N+1: 1-idx
    for v, u in E:  # construct a undirected graph
        G[v] += [u]
        G[u] += [v]
    bridges = 0
    for v, u in E:
        g = deepcopy(G)  # subgraph of G except E(v, u)
        g[v].remove(u)
        g[u].remove(v)
        seen = [0] * (N + 1)
        dfs(1)  # search from vertex 1
        bridges += 1 if 0 in seen[1:] else 0
    print(bridges)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC075C - Bridge
# find the number of bridges in a given undirected connected graph
# bridge := an edge whose removal disconnects a graph
import sys
from copy import deepcopy

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, g: "List[List[int]]", seen: "List[int]") -> None:
    seen[v] = 1  # make vertex v searched
    for u in g[v]:
        if not seen[u]:
            dfs(u, g, seen)


def main():
    N, M = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]
    for v, u in E:  # construct a graph
        G[v] += [u]
        G[u] += [v]
    bridges = 0
    for v, u in E:
        g = deepcopy(G)  # subgraph of G withiout E(v, u)
        g[v].remove(u)
        g[u].remove(v)
        seen = [0] * (N + 1)
        dfs(1, g, seen)
        bridges += 1 if 0 in seen[1:] else 0
    print(bridges)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
import copy
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
ans=0
for i in range(m):
    ltmp=copy.deepcopy(l)
    ltmp=ltmp[:i]+ltmp[i+1:]
    UF=UnionFind(n)
    for j in ltmp:
        UF.Unite(j[0]-1,j[1]-1)
    if UF.Count(0)!=n:ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
 
lines = []
for _ in range(M):
	lines.append(list(map(lambda x: int(x) - 1, input().split())))
 
def root(x):
	if par[x] == x:
		return x
	
	par[x] = root(par[x])
	return par[x]
 
def unite(x, y):
	rx = root(x)
	ry = root(y)
	if rx != ry:
		par[rx] = ry
 
def same(x, y):
	rx = root(x)
	ry = root(y)
	return rx == ry
 
 
ans = 0
 
for i in range(M):
	par = [x for x in range(N)]
	
	for j in range(M):
		if i != j:
			unite(lines[j][0], lines[j][1])
	
	flag = True
	for j in range(1, N):
		if not same(0, j):
			flag = False
	if not flag:
		ans += 1
 
print(ans)

Submission status: Accepted

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

lines = []
for _ in range(M):
	lines.append(list(map(lambda x: int(x) - 1, input().split())))

def root(x):
	if par[x] == x:
		return x
	
	par[x] = root(par[x])
	return par[x]

def unite(x, y):
	rx = root(x)
	ry = root(y)
	if rx != ry:
		par[rx] = ry

def same(x, y):
	rx = root(x)
	ry = root(y)
	return rx == ry


ans = 0

for i in range(M):
	par = [x for x in range(N)]
	
	for j in range(M):
		if i != j:
			unite(lines[j][0], lines[j][1])
	
	flag = True
	for j in range(1, N):
		if not same(0, j):
			flag = False
	if not flag:
		ans += 1

print(ans)