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:
# input
N, M = map(int, input().split())
edge_lst = [list(map(int, input().split())) for i in range(M)]

adj_matrix = {} # グラフを辺列挙 -> 隣接行列に変換
for i in range(1, N + 1):
    adj_lst = []
    for j in range(M):
        if edge_lst[j][0] == i:
            adj_lst.append(edge_lst[j][1])
        if edge_lst[j][1] == i:
            adj_lst.append(edge_lst[j][0])
    adj_matrix[i] = adj_lst

# root: 葉を探索中の根
# next: 次に探索される葉
# count: 探索回数
# order[1,...,N]: 頂点iが探索された順番
# low[1,...,N]: 頂点iから訪問可能な頂点のうち、最も上にある頂点の探索順

def dfs_bridge(graph, root, next, count, low, order, bridges): # graphは隣接行列表示
    count += 1
    order[next] = count
    low[next] = order[next]

    for w in graph[next]: # vと隣接している頂点
        if order[w] == -1: # wは未訪問
            dfs_bridge(graph, next, w, count, low, order, bridges)

            low[next] = min(low[next], low[w])
            if low[w] == order[w]: # 頂点w以降から頂点v以前に戻れない
                bridges.append((next, w))
        elif w != root: # 一つ前の頂点（自明に戻れる頂点）より前に戻れる場合
            low[next] = min(low[next], order[w])

def get_bridges(graph):
    bridges = []
    count = 0
    low = {n: -1 for n in graph.keys()}
    order = low.copy()

    for n in graph.keys():
        dfs_bridge(graph, n, n, count, low, order, bridges)
    
    return(bridges) # 橋 = (node, node)のタプルのリスト
            
ans = get_bridges(adj_matrix)
print(len(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

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

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

renketu = 0
for m in range(M): #取り除く辺
    D = defaultdict(list) #探索準備
    for l in L[:m]+L[m+1:]:
        a,b = l[0],l[1]
        D[a].append(b)
        D[b].append(a)
    Q = queue.Queue()
    Q.put(L[0][0])
    walked = [L[0][0]]
    #print(walked,end="→")
    while(True):
        now = Q.get()
        for d in D[now]:
            if d not in walked:
                Q.put(d)
                walked.append(d)
        #print(walked,end="→")
        if len(walked)==N:break
        if Q.empty():break
    if len(walked)==N:
        #print("{} is not Bridge".format(L[m]))
        renketu+=1
    #print()
        
print(M-renketu)

Submission status: Accepted

Solution code:
class UnionFind():
    # https://qiita.com/hukuhuku11111a1/items/1bbf67d90630552eb512
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        while 1:
            i = self.table[x]
            if i < 0:
                return x
            x = i

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

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

result = 0

for a1, b1 in ab:
    uf = UnionFind(N + 1)
    for a, b in ab:
        if (a, b) == (a1, b1):
            continue
        uf.union(a, b)
    rs = set([])
    for i in range(1, N + 1):
        rs.add(uf.find(i))
    if len(rs) > 1:
        result += 1

print(result)

Submission status: Accepted

Solution code:
class UnionFind():
    # https://qiita.com/hukuhuku11111a1/items/1bbf67d90630552eb512
    def __init__(self, size):
        self.table = [-1] * 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 = [int(_) for _ in input().split()]
ab = [[int(_) for _ in input().split()] for _ in range(M)]

result = 0

for a1, b1 in ab:
    uf = UnionFind(N + 1)
    for a, b in ab:
        if (a, b) == (a1, b1):
            continue
        uf.union(a, b)
    rs = set([])
    for i in range(1, N + 1):
        rs.add(uf.find(i))
    if len(rs) > 1:
        result += 1

print(result)

Submission status: Accepted

Solution code:
class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す 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,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)

N,M=map(int,input().split())
table=[]
for i in range(M):
    a,b=map(int,input().split())
    table.append([a-1,b-1])
ans =0
for i in range(M):
    K=Unionfindtree(N)
    for j in range(M):
        if i==j:
            continue
        a,b=table[j]
        K.union(a,b)
    flag=False
    for k in range(1,N):
        if not K.connect(0,k):
            flag=True
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

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

adj_matrix = {} # グラフを辺列挙 -> 隣接行列に変換
for i in range(1, N + 1):
    adj_lst = []
    for j in range(M):
        if edge_lst[j][0] == i:
            adj_lst.append(edge_lst[j][1])
        if edge_lst[j][1] == i:
            adj_lst.append(edge_lst[j][0])
    adj_matrix[i] = adj_lst

# root: 葉を探索中の根
# next: 次に探索される葉
# count: 探索回数
# order[1,...,N]: 頂点iが探索された順番
# low[1,...,N]: 頂点iから訪問可能な頂点のうち、最も上にある頂点の探索順

def dfs_bridge(graph, root, next, count, low, order, bridges): # graph is represented by adj. matrix
    count += 1
    order[next] = count
    low[next] = order[next]

    for w in graph[next]: # neighbors of v
        if order[w] == -1: # if w is not visited yet
            dfs_bridge(graph, next, w, count, low, order, bridges)

            low[next] = min(low[next], low[w])
            if low[w] == order[w]: # 頂点w以降から頂点v以前に戻れない
                bridges.append((next, w))
        elif w != root: # 一つ前の頂点（自明に戻れる頂点）より前に戻れる場合
            low[next] = min(low[next], order[w])

def get_bridges(graph):
    bridges = []
    count = 0
    low = {n: -1 for n in graph.keys()}
    order = low.copy()

    for n in graph.keys():
        dfs_bridge(graph, n, n, count, low, order, bridges)
    
    return(bridges) # List of [node, node] lists for all bridges in G
            
ans = get_bridges(adj_matrix)
print(len(ans))

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
A = []
B = []
G = [[-1] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1][b - 1] = 1
    G[b - 1][a - 1] = 1
    A.append(a - 1)
    B.append(b - 1)


def BFS(G):  # 連結か判定する関数
    """
    >>> BFS([[-1, 1, 1], [1, -1, 1], [1, 1, -1]])
    True
    >>> BFS([[-1,1,-1], [1,-1,-1], [-1,-1,-1]])
    False
    >>> BFS([[-1,1,-1,-1], [1,-1,1,-1], [-1,1,-1,1], [-1,-1,1,-1]])
    True
    """
    q = deque()
    q.append(0)
    visited = [False] * len(G)
    while len(q) != 0:
        p = q.popleft()
        for j in range(len(G)):
            if G[p][j] == 1 and not visited[j]:
                q.append(j)
                visited[j] = True
    if False in visited:
        return False
    else:
        return True


count = 0
for i in range(M):
    G[A[i]][B[i]] = -1
    G[B[i]][A[i]] = -1
    if not BFS(G):
        count += 1
    G[A[i]][B[i]] = 1
    G[B[i]][A[i]] = 1
print(count)

Submission status: Accepted

Solution code:
from itertools import combinations
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]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

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

ans = 0
for i in range(m):
	if i == 0:
		new_edges = edges[1:]
	elif i == m - 1:
		new_edges = edges[:m - 1]
	else:
		new_edges = edges[:i] + edges[i + 1:]
	uf = UnionFind(n)
	for e in new_edges:
		uf.union(e[0] - 1, e[1] - 1)
	for a, b in combinations(range(n), r=2):
		if uf.find(a) != uf.find(b):
			ans += 1
			break

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
count = 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:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edge = [[0]*n for _ in range(n)]
a = []
b = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    a.append(x)
    b.append(y)
    edge[x][y] = 1
    edge[y][x] = 1

def bfs():
    q = [0]
    visit = [False]*n
    visit[0] = True
    while q:
        x = q[0]
        q.pop(0)
        for i in range(n):
            if not visit[i] and edge[x][i] == 1:
                q.append(i)
                visit[i] = True
    return len(list(filter(lambda x:x, visit)))

ans = 0
for i in range(m):
    edge[a[i]][b[i]] = 0
    edge[b[i]][a[i]] = 0
    if bfs() < n:
        ans += 1
    edge[a[i]][b[i]] = 1
    edge[b[i]][a[i]] = 1

print(ans)

Submission status: Accepted

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

H = [[0 for _ in range(n)] for _ in range(n) ]
edge_list = []

for _ in range(m):
    a, b = map(int,input().split())
    edge_list.append([a,b])
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
visited = [0 for _ in range(n)]

def dfs(node):
    visited[node] = 1
    for node_,edge_ in enumerate(H[node]):
        if edge_ == 1:
            if visited[node_] == 1:
                continue
            dfs(node_)
ans = 0
for _ in edge_list:
    H[_[0] -1][_[1] - 1] = 0
    H[_[1] -1][_[0] - 1] = 0
    
    dfs(1)
    if 0 in visited:
        ans += 1
    H[_[0] -1][_[1] - 1] = 1
    H[_[1] -1][_[0] - 1] = 1
    visited = [0 for _ in range(n)]
print(ans)

Submission status: Accepted

Solution code:
def dfs(now):
    if vis[now]:
        return 0
    vis[now]=1
    for i in range(n):
        if graph[now][i]:
            dfs(i)
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
vis=[0]*n
ans=0
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=0
    graph[edge[i][1]-1][edge[i][0]-1]=0
    vis=[0]*n
    dfs(0)
    connect=False
    for j in range(n):
        if vis[j]==0:
            connect=True
    if connect:
        ans+=1
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N,M = map(int, input().split())
g = [[False]*(N+1) for _ in range(N+1)] # こうしないと同じ配列が参照される
a = [0]*(M+1)
b = [0]*(M+1)
for i in range(1, M+1):
  a[i],b[i] = map(int, input().split())
  g[a[i]][b[i]] = g[b[i]][a[i]] = True

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

  for v2 in range(1, N+1):
    if not g[v][v2]: continue
    # 一度訪れてその先の経路も全て visit してるはずなので
    if visited[v2]: continue
    dfs(v2)

count = 0
for i in range(1, M+1):
  visited = [True] + [False]*N
  g[a[i]][b[i]] = g[b[i]][a[i]] = False
  dfs(1)
  if not all(visited): count += 1
  g[a[i]][b[i]] = g[b[i]][a[i]]= True

print(count)

Submission status: Accepted

Solution code:
def dfs(now):
    if vis[now]==1:#既に訪問済みであればreturn
        return 0
    vis[now]=1#訪問した記録をつける
    for i in range(n):
        if graph[now][i]==1:#接続していれば、移動
            dfs(i)
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]#入力値を受け取る
graph=[[0 for i in range(n)]for i in range(n)]
vis=[0]*n#既にある頂点を訪問したか管理する配列
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1#グラフを生成
    graph[edge[i][1]-1][edge[i][0]-1]=1
ans=0
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=0#ある辺を消去
    graph[edge[i][1]-1][edge[i][0]-1]=0
    vis=[0]*n
    dfs(0)
    connect=False#全ての点が繋がっているか判断する値
    for j in range(n):
        if vis[j]==0:#訪問していない点があればcout
            connect=True
    if connect:
        ans+=1
    graph[edge[i][0]-1][edge[i][1]-1]=1#消した辺をもとに戻す
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Submission status: Accepted

Solution code:
def dfs(now):
    if vis[now]==1:
        return 0
    vis[now]=1
    for i in range(n):
        if graph[now][i]==1:
            dfs(i)
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
vis=[0]*n
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
ans=0
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=0
    graph[edge[i][1]-1][edge[i][0]-1]=0
    vis=[0]*n
    dfs(0)
    connect=False
    for j in range(n):
        if vis[j]==0:
            connect=True
    if connect:
        ans+=1
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(M):
    visited = [0]*(N+1)
    p = [edges[i][0]]
    visited[p[0]] = 1
    p.extend(graph[edges[i][0]])
    p.remove(edges[i][1])
    for k in p:
        if visited[k]:
            continue
        visited[k] = 1
        p.extend(graph[k])
    if visited[edges[i][1]] == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
      
N,M=map(int,input().split())
B=[]
for i in range(M):
  a,b=map(int,input().split())
  B.append((a,b))

def solve(x):
  a,b=B[x]
  uf=UnionFind(N+1)
  for i in range(M):
    if i!=x:
      uf.union(B[i][0],B[i][1])
  if uf.find(a)==uf.find(b):
    return False
  else:
    return True

ans=0
for i in range(M):
  if solve(i):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
connectdic = {}
for i in range(1,N+1):
    connectdic[i] = set()

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

count = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if j not in connectdic[i]:
            continue
        tempdic = copy.deepcopy(connectdic)
        tempdic[i].remove(j)
        tempdic[j].remove(i)
        startset = set([1])
        check = set([1])
        while len(startset) > 0:
            nextset = set()
            for k in startset:
                for l in tempdic[k]:
                    if l not in check:
                        check.add(l)
                        nextset.add(l)
            startset = nextset
        if len(check) != N:
            count += 1
print(count)

Submission status: Accepted

Solution code:

def DFS( graph, bridge, node, count, parent, low, pre):
    pre[node] = count
    count+= 1
    low[node] = pre[node]
    for n in graph[node]:
        if pre[n] == -1:
            low[node] = min( low[node], DFS( graph, bridge, n, count, node, low, pre))
            if low[n] == pre[n]:
                bridge.append( (node, n))
        else:
            if n == parent:
                continue
            low[node] = min( low[node], low[n])
    return low[node]

N, M = [int(x) for x in input().split()]
graph = [ [] for i in range(N)]
for i in range(M):
    a, b = [int(x) for x in input().split()]
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
bridge = []
low = [-1]*N
pre = [-1]*N
DFS( graph, bridge, 0, 0, -1, low, pre)
print( len(bridge))

Submission status: Accepted

Solution code:
def dfs(v):
    visited[v]=1#訪問済みとする
    for i in range(n):#全ての遷移先を調べる
        if connect[v][i]==0:#接続していない
            continue
        if visited[i]==1:#既に訪問済み
            continue
        dfs(i)
n,m=map(int,input().split())
edge=[[int(i)for i in input().split()]for i in range(m)]
connect=[[0 for i in range(n)]for i in range(n)]#接続状況を管理する配列
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1#接続状況を格納
    connect[edge[i][1]-1][edge[i][0]-1]=1
visited=[0]*n#既にその頂点を訪問したか管理する配列
ans=0
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=0#接続を取り除く
    connect[edge[i][1]-1][edge[i][0]-1]=0
    for j in range(n):
        visited[j]=0
    dfs(0)
    brdge=False
    for j in range(n):
        if visited[j]==0:
            brdge=True
    if brdge:
        ans+=1
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Submission status: Accepted

Solution code:
def dfs(v):
    visited[v]=1
    for i in range(n):
        if connect[v][i]==0:#接続していない
            continue
        if visited[i]==1:#既に訪問済み
            continue
        dfs(i)
n,m=map(int,input().split())
edge=[[int(i)for i in input().split()]for i in range(m)]
connect=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1#接続状況を格納する配列
    connect[edge[i][1]-1][edge[i][0]-1]=1
visited=[0]*n#既にその頂点を訪問したか管理する配列
ans=0
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=0
    connect[edge[i][1]-1][edge[i][0]-1]=0
    for j in range(n):
        visited[j]=0
    dfs(0)
    brdge=False
    for j in range(n):
        if visited[j]==0:
            brdge=True
    if brdge:
        ans+=1
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
print(ans)

Submission status: Accepted

Solution code:
import copy


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

    for m in range(M):
        a, b = E[m]
        graph[a].append(b)
        graph[b].append(a)

    def dfs(v, g):
        if visited[v] == True:
            return
        visited[v] = True
        for i in g[v]:
            dfs(i, g)

    def is_all_visited(v):
        for i in range(1, N + 1):
            if v[i]:
                pass
            else:
                return False
        return True

    ans = 0
    for j in range(M):
        y, z = E[j]
        visited = [False] * (N + 1)
        tmp = copy.deepcopy(graph)
        tmp[y].remove(z)
        tmp[z].remove(y)
        dfs(1, tmp)
        if is_all_visited(visited):
            pass
        else:
            ans += 1

    return ans


print(m())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i 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] * (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 x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uf.union(AB[j][0], AB[j][1])
    for k in range(N):
        uf.find(k+1)
    if len(set(uf.par)) != 2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A,B,Ans = [[] for _ in range(N)],[],0
def s(v,a,b):
    visited[v] = True
    for n in A[v]:
        if not visited[n] and set([v,n]) != set([a,b]):
            s(n,a,b)

for i in range(M):
    a,b = map(int,input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)
    B.append((a-1,b-1))
for i in range(M):
    visited = [True]+[False]*(N-1)
    a,b = B[i]
    s(0,a,b)
    if visited != [True]*N:
        Ans += 1
print(Ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

parent = [i for i in range(N)]
rank = [0] * N
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
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

ans = 0
for i in range(M):
    parent = [i for i in range(N)]
    rank = [0] * N
    for j,(a,b) in enumerate(src):
        if i == j: continue
        unite(a,b)
    if len(set([root(i) for i in range(N)])) > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

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

adjacent = np.zeros((N, N))
for l in L:
    adjacent[l[0] - 1, l[1] - 1] = 1
    adjacent[l[1] - 1, l[0] - 1] = 1
# print(adjacent, end='\n\n')

pre = [-1 for _ in range(N)]
low = [-1 for _ in range(N)]
v = k = 0
ans = 0


def dfs(v, pre, low, k, parent):
    global ans
    pre[v] = k
    k += 1
    low[v] = pre[v]
    for to, n in enumerate(adjacent[v, :]):
        if n == 1:
            if pre[to] == -1:
                # destination has not been visited
                # visit destination and update low[v]
                # print('-----', v, '-------')
                # print(pre, low)
                low[v] = min(low[v], dfs(to, pre, low, k, v))
                if low[to] == pre[to]:
                    ans += 1
                    # print(v + 1, to + 1)
            else:
                # visited
                if to == parent:
                    pass
                else:
                    low[v] = min(low[v], low[to])

    return low[v]


dfs(v, pre, low, k, -1)
# print(pre, low)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
t, d = {}, []

if n > m:
    print(m)
else:
    for i in range(m):
        a, b = map(int, input().split())
        t[a] = t.get(a, 0) + 1
        t[b] = t.get(b, 0) + 1
        d.append((a, b))

    while True:
        b = 0
        for i in t:
            if t[i] == 1:
                for j in d:
                    if j[0] == i or j[1] == i:
                        for k in j:
                            if k != i and t[k] > 1:
                                t[k] -= 1
                                t[i] = 0
                                b += 1

        if b == 0:
            break

    b = 0
    for i in t:
        if t[i] == 0:
            b += 1
    print(b)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


def is_visited(graph):
    visited = [False] * len(graph[0])

    def dfs(x: int):
        if visited[x]:
            return

        visited[x] = True

        for i in range(n):
            if graph[x][i]:
                dfs(i)

    dfs(0)
    return visited


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    graph = [[0 for i in range(n)] for j in range(n)]

    # See:
    # https://img.atcoder.jp/abc075/editorial.pdf
    # https://www.youtube.com/watch?v=VJntQuR2zNI
    for i in range(m):
        line = list(map(int, input().split()))
        a[i] = line[0] - 1
        b[i] = line[1] - 1
        graph[a[i]][b[i]] = True
        graph[b[i]][a[i]] = True

    bridge_count = 0

    for j in range(m):
        graph[a[j]][b[j]] = False
        graph[b[j]][a[j]] = False

        if False in is_visited(graph):
            bridge_count += 1

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

    print(bridge_count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


def dfs(x: int):
    global visited, graph

    if visited[x]:
        return

    visited[x] = True

    for i in range(n):
        if graph[x][i]:
            dfs(i)


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    graph = [[0 for i in range(n)] for j in range(n)]

    # See:
    # https://img.atcoder.jp/abc075/editorial.pdf
    # https://www.youtube.com/watch?v=VJntQuR2zNI
    for i in range(m):
        line = list(map(int, input().split()))
        a[i] = line[0] - 1
        b[i] = line[1] - 1
        graph[a[i]][b[i]] = True
        graph[b[i]][a[i]] = True

    bridge_count = 0

    for j in range(m):
        graph[a[j]][b[j]] = False
        graph[b[j]][a[j]] = False

        visited = [False] * len(graph[0])
        dfs(0)

        if False in visited:
            bridge_count += 1

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

    print(bridge_count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


def dfs(x: int):
    if visited[x]:
        return

    visited[x] = True

    for i in range(n):
        if graph[x][i]:
            dfs(i)


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    graph = [[0 for i in range(n)] for j in range(n)]

    # See:
    # https://img.atcoder.jp/abc075/editorial.pdf
    # https://www.youtube.com/watch?v=VJntQuR2zNI
    for i in range(m):
        line = list(map(int, input().split()))
        a[i] = line[0] - 1
        b[i] = line[1] - 1
        graph[a[i]][b[i]] = True
        graph[b[i]][a[i]] = True

    bridge_count = 0

    for j in range(m):
        graph[a[j]][b[j]] = False
        graph[b[j]][a[j]] = False

        visited = [False] * len(graph[0])
        dfs(0)

        if False in visited:
            bridge_count += 1

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

    print(bridge_count)

Submission status: Accepted

Solution code:
import collections as col

graph = col.defaultdict(set)
used = set()
ans = 0

def dfs(x,t):
    if x == t:
        return True
    used.add(x)
    ret = False
    for y in graph[x]:
        if y not in used:
            ret = ret or dfs(y,t)
    return ret

def solve():
    n,m = map(int,input().split())
    global used,ans
    for i in range(0,m):
        a,b = map(int,input().split())
        graph[a].add(b)
        graph[b].add(a)
    for a in graph:
        for b in graph[a]:
            graph[a].remove(b)
            used = set()
            if not dfs(a,b):
                ans += 1
            graph[a].add(b)
    print(ans//2)
    return

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [list(map(int, input().split())) for k in range(M)]

ans = 0
for k in range(M):
    F = E[:k]+E[k+1:]
    D = [[10**9+7 for l in range(N)] for m in range(N)]
    for p in range(N):
        D[p][p] = 0
    for n in F:
        D[n[0]-1][n[1]-1] = D[n[1]-1][n[0]-1] = 1
    for s in range(N):
        for t in range(N):
            for u in range(N):
                if D[t][u] > D[t][s] + D[s][u]:
                    D[t][u] = D[t][s] + D[s][u]
    f = 0
    for p in range(N):
        for q in range(N):
            if D[p][q] > N:
                f = 1
    ans += f
print(ans)

Submission status: Accepted

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

def dfs(v,a,b):
    visited[v] = True
    for n in E1[v]:
        if not visited[n] and set([v,n]) != set([a,b]):
            dfs(n,a,b)


E1 = [[] for _ in range(N)]
E2 = []
Ans = 0

for i in range(M):
    a,b = map(int,input().split())
    E1[a-1].append(b-1)
    E1[b-1].append(a-1)
    E2.append((a-1,b-1))
for i in range(M):
    visited = [True]+[False]*(N-1)
    a,b = E2[i]
    dfs(0,a,b)
    if visited != [True]*N:
        Ans += 1
print(Ans)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
a,b=[0 for i in range(m)],[0 for i in range(m)]
g = [[0 for i in range(n)] for j in range(n)]
ans = 0

def dfs(v,visited):
    if visited[v]:
        return
    visited[v] = True 
    for i in range(n):
        if g[v][i]:
            dfs(i,visited)

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

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

    dfs(0,visited)

    if not all(visited):
        ans += 1

    g[a[i]][b[i]], g[b[i]][a[i]] = True, True 
print(ans)