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:
# ABC075C - Bridge
# find the number of bridges in a given undirected connected graph
# bridge := an edge whose removal disconnects a graph
def dfs(start: int) -> None:
    seen[start] = 1  # make vertex v searched
    stack = [start]
    while stack:
        v = stack.pop()
        for u in g[v]:
            if not seen[u]:
                seen[u] = 1
                stack.append(u)


def main():  # O(M(N + M))
    global g, seen
    N, M, *E = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        G[v].append(u), G[u].append(v)
    bridges = 0
    for v, u in zip(*[iter(E)] * 2):
        g = [v.copy() for v in 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:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    class Lowlink(object):
        """
        construct: O(V+E)
        """
        def __init__(self,edges,root=0):
            """
            edges: list of list of int (adjacency list)
            root: int
            """
            # initialization
            self.__n=len(edges)
            self.__edges=edges
            self.__count=0
            self.__ord=[-1]*self.__n
            self.__low=[-1]*self.__n
            self.__bridge=[]
            self.__articulation=[]
            # construct
            self.__dfs(root,-1)

        def __dfs(self,v,p): # p:parent
            self.__ord[v]=self.__count
            self.__low[v]=self.__count
            self.__count+=1
            isArticulation=False
            count=0 # DFS treeの子の数(rootのarticulate判定に必要)
            for u in self.__edges[v]:
                if self.__ord[u]==-1: # まだ見てない
                    count+=1
                    self.__dfs(u,v)
                    self.__low[v]=min(self.__low[v],self.__low[u])
                    if (self.__ord[v]<self.__low[u]): self.__bridge.append([min(u,v),max(u,v)])
                    if (p!=-1 and self.__ord[v]<=self.__low[u]): isArticulation=True
                elif u!=p: # uは見たけどvuは通ってない(=後退辺(backward edge))
                    self.__low[v]=min(self.__low[v],self.__low[u])
            if (p==-1 and count>=2): isArticulation=True
            if isArticulation: self.__articulation.append(v)

        @property
        def bridge(self):
            return self.__bridge

        @property
        def articulation(self):
            return self.__articulation

    # input
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(lambda x:int(x)-1,input().split())
        edges[u].append(v)
        edges[v].append(u)
    low=Lowlink(edges)
    print(len(low.bridge))

resolve()

Submission status: Accepted

Solution code:
# ABC075c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def root(x):
    if(tree[x] == x):
        return x
    tree[x] = root(tree[x])
    return tree[x]  # 経路圧縮


def same(x, y):  # xとyが同じ木に属するか
    return root(x) == root(y)


def unite(x, y):
    x = root(x)
    y = root(y)
    if(x == y):
        return
    tree[x] = y


ans = 0
for i in range(m):
    # print('init')
    tree = []
    for k in range(n+1):
        tree.append(k)
    for j in range(m):
        if (i == j):
            continue
        # print(a[j])
        unite(a[j][0], a[j][1])
    flag = True
    for j in range(1, n+1):
        for k in range(j + 1, n+1):
            if (not same(j, k)):
                flag = False
    if (not flag):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
from copy import deepcopy
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  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(N)]
"""

class Node():
    def __init__(self, ch):
        self.ch_list = [ch]
        self.visited = False

N, M = map(int, sys.stdin.readline().split())
node_list = [0] * N

edge_list =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(M)]
for edge in edge_list:
    # リストのインデックスとnodeのidを統一しておく
    edge[0] -= 1
    edge[1] -= 1
for edge in edge_list:
    a, b = edge
    if node_list[a] == 0:
        node_list[a] = Node(b)
    else:
        if b not in node_list[a].ch_list:
            node_list[a].ch_list.append(b)

    if node_list[b] == 0:
        node_list[b] = Node(a)
    else:
        if a not in node_list[b].ch_list:
            node_list[b].ch_list.append(a)

def dfs(current_idx, ch_num, n_list):
    current = n_list[current_idx]
    if current == 0:
        return ch_num
    if current.visited:
        return ch_num
    ch_num += 1
    current.visited = True
    # print(current_idx + 1, list(map(lambda x: x + 1, current.ch_list)), ch_num)
    for idx in current.ch_list:
        # print("before", current_idx + 1, idx + 1, ch_num)
        ch_num = dfs(idx, ch_num, n_list)
        # print("after", current_idx + 1, idx + 1, ch_num)
    return ch_num

base_num = dfs(0, 0, deepcopy(node_list))

cnt = 0
for edge in edge_list:
    nl = deepcopy(node_list)
    a, b = edge
    nl[a].ch_list.remove((b))
    nl[b].ch_list.remove((a))
    num = dfs(0, 0, nl)
    # print(a + 1, b + 1, num)
    if num != base_num:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())  # N頂点, M個の辺

graph = [[] for _ in range(N)]
edges = []

# グラフを定義する
# あとで辺の情報を使いたいから辺を格納するリストを用意する
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
    edges.append((a, b))


ans = 0
# ある辺を取り除いても全頂点に到達できるかを幅優先で調べる、最後にその辺を戻してあげる
for a, b in edges:
    graph[a].remove(b)
    graph[b].remove(a)
    q = deque([0])  # 開始のノード
    flag = [False] * N

    while len(q):
        v = q.pop()

        flag[v] = True  # 部分木の根を到達済みにする
        for e in graph[v]:  # vを根にもつノード全てに操作をする
            # graphは子のみを格納するのではなく、そのノードから出ている辺を
            # 親とか子供とか関係なく全て格納してしまうため、親の方向に
            # 対して走っていかないようにflagで管理する
            if flag[e]:  # 頂点eがvの親であればスルー
                continue

            # この時点でeはvの子供であることが確定する
            q.append(e)

    graph[a].append(b)
    graph[b].append(a)
    if not all(flag):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())  # N頂点, M個の辺

graph = [[] for _ in range(N)]
edges = []

# グラフを定義する
# あとで辺の情報を使いたいから辺を格納するリストを用意する
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
    edges.append((a, b))


ans = 0
# ある辺を取り除いても全頂点に到達できるかを幅優先で調べる、最後にその辺を戻してあげる
for a, b in edges:
    graph[a].remove(b)
    graph[b].remove(a)
    q = deque([0])  # 開始のノード
    flag = [False] * N
    # 幅優先で1回しか到達できない頂点を調べる（親もカウントするならちょうど二回か？）
    while len(q):
        v = q.pop()

        flag[v] = True  # 部分木の根を到達済みにする
        for e in graph[v]:  # vを根にもつノード全てに操作をする
            # graphは子のみを格納するのではなく、そのノードから出ている辺を
            # 親とか子供とか関係なく全て格納してしまうため、親の方向に
            # 対して伝播をしないようにflagで管理する
            if flag[e]:  # 頂点eがvの親であればスルー
                continue

            # この時点でeはvの子供であることが確定する
            q.append(e)

    graph[a].append(b)
    graph[b].append(a)
    if not all(flag):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(m)]
c=0
for x in e:
  l=list(range(n))
  for y in e:
    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:c+=1
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(m)]

cnt=0
for x in e:
  l=list(range(n))
  for y in e:
    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:cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
def isHashi(a,b):
    visited = {}
    visited[a] = 1
    go = G[a]
    path = []
    for i in go:
        if i != b:
            path.append(i)
    flag = 0
    while path != []:
        to = path.pop()
        visited[to] = 1
        for i in G[to]:
            if not i in visited:
                visited[i] = 1
                if i == b:
                    flag = 1
                path.append(i)
    if flag == 0:
        return 1
    else:
        return 0
        
    
N,M = map(int,input().split())

G = [[0]*(N+1) for i in range(N+1)]
E = []

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

ans = 0
for i in range(M):
    a,b = E[i]
    if isHashi(a,b) == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 12 10:38:04 2019
C - Bridge
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
300
 点
@author: justwah
use union find
"""

import sys
read = sys.stdin.readline

n, m = map(int, input().split())    # single line use regular input() is faster

l = [list(tuple(map(int, read().split()))) for i in range(m)]   #multiple lines use sys.stdin.readline faster

def root(x): #recursively find root for a node
    if parent[x] < 0: # if at root, return self
        return x
    else:
        parent[x] = root(parent[x])  # while searching rejoint queried node to a common parent for hierarchical tree
        return parent[x]
    
def merge(a, b):
    a = root(a)
    b = root(b)
    if rank[a] < rank[b]: # joint lower rank node to a higher rank one
        parent[a] = b
    else:
        parent[b] = a
        if rank[a] == rank[b]: # rank only change if two same rank node joined
            rank[a] +=1    
    return

score = 0

for i in range(m):
    parent = [-1]*(n+1)
    rank = [0]*(n+1)
    for j, (a, b) in enumerate(l[i:]+l[:i]): #iteraete from different starting point - test different last bridge
        a = root(a)
        b = root(b)
        if a != b:
            merge(a, b)
        else:
            if j == (len(l)-1):
                score += 1 # if the last bridge is redundant, +1

print(m-score)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 12 10:38:04 2019
C - Bridge
実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 
300
 点
@author: justwah
"""

import sys
read = sys.stdin.readline

n, m = map(int, input().split())    # single line use regular input() is faster

l = [list(tuple(map(int, read().split()))) for i in range(m)]   #multiple lines use sys.stdin.readline faster

def root(x): #recursively find root for a node
    if parent[x] < 0: # if at root, return self
        return x
    else:
        parent[x] = root(parent[x])  # while searching rejoint queried node to a common parent for hierarchical tree
        return parent[x]
    
def merge(a, b):
    a = root(a)
    b = root(b)
    if rank[a] < rank[b]: # joint lower rank node to a higher rank one
        parent[a] = b
    else:
        parent[b] = a
        if rank[a] == rank[b]: # rank only change if two same rank node joined
            rank[a] +=1    
    return

score = 0

for i in range(m):
    parent = [-1]*(n+1)
    rank = [0]*(n+1)
    first = l[0]
    l = l[1:]
    l.append(first)
    for i, (a, b) in enumerate(l):
        a = root(a)
        b = root(b)
        if a != b:
            merge(a, b)
        else:
            if i == (len(l)-1):
                score += 1

print(m-score)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
list_a = []
list_b = []
g = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    list_a.append(a-1)
    list_b.append(b-1)
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1


def dfs(v):
    seen[v] = 1 #vを訪問済みにする
    ret = 1
    for v2 in range(N):
        if g[v][v2] == 1 and seen[v2] == 0:
           
            dfs(v2)
    if seen == [1] * N: #すべての頂点を訪問したらretを返す
        ret = 0

    return ret

ans = 0
for i in range(M):
    seen = [0] * N
    g[list_a[i]][list_b[i]] = 0
    g[list_b[i]][list_a[i]] = 0
    ans += dfs(0)
    g[list_a[i]][list_b[i]] = 1
    g[list_b[i]][list_a[i]] = 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
node_list = [[0] * n for i in range(n)]
count = 0

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

flg = True
count = 0
while flg:
    flg = False
    for i in range(n):
        if node_list[i].count(1) == 1:
            count += 1
            j = node_list[i].index(1)
            node_list[i][j] = 0
            node_list[j][i] = 0
            flg = True

print(count)

Submission status: Accepted

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

def dfs(v, end):
    if visited[v]:
        return False
    visited[v] = True
    
    for e in graph[v]:
        res = dfs(e, end)
        if res:
            return True
    if v == end:
        return True
    else:
        return False
        

if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [None]*M
    graph = [[] for _ in range(N)]
    
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        A[i] = [a, b]
        graph[a].append(b)
        graph[b].append(a)
    
    
    count = 0
    for a, b in A:
        graph[a].remove(b)
        graph[b].remove(a)
        visited = [False]*N
        if not dfs(a, b):
            count += 1
        graph[a].append(b)
        graph[b].append(a)
    print(count)

Submission status: Accepted

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

def dfs(E,visited,v):
  visited[v] = 1
  for u in E[v]:
    if not visited[u]:
      dfs(E,visited,u)
  return sum(visited)

ans = 0
for i in range(M):
  Gtmp = G[:]
  del Gtmp[i:i+1]
  #print(Gtmp)
  E = [set() for _ in range(N+1)]
  for g in Gtmp:
    E[g[0]].add(g[1])
    E[g[1]].add(g[0])
  #print(E)
  visited = [0] * (N+1)
  if dfs(E,visited,1) < N:
    ans += 1
print(ans)

Submission status: Accepted

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

T = [[0 for _ in range(N)] for _ in range(N)]

for i in range(M):
	a,b = E[i]
	T[a-1][b-1] = 1
	T[b-1][a-1] = 1

def bfs(table, flg, q):
	c = q.pop(0)
	flg[c-1] = 1

	NN = [ind+1 for ind in range(N) if table[c-1][ind] == 1]
	for n in NN:
		if flg[n-1] == 0:
			q.append(n)
	
	if len(q) == 0:
		return flg.count(0)

	return bfs(table, flg, q)

ans = 0

for i in range(M):
	a,b = E[i]
	T[a-1][b-1] = 0
	T[b-1][a-1] = 0
	
	flg = [0 for _ in range(N)]

	cnt = bfs(T, flg, [1])

	if cnt > 0:
		ans += 1

	T[a-1][b-1] = 1
	T[b-1][a-1] = 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
T=[input().split()for _ in range(M)]
class U(list):
 def __init__(self,n):
  super().__init__(range(n))
 def f(self,i):
  if i==self[i]:return i
  self[i]=self.f(self[i])
  return self[i]
 def u(self,i,j):
  self[self.f(i)]=self.f(j)
c=0
for i in range(M):
 u=U(N)
 for j in range(M):
  if i!=j:p,q=T[j];u.u(int(p)-1,int(q)-1)
 for j in range(N):
  u.f(j)
 c+=len(set(u))==2
print(c)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

class UF(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        '''
        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 のグループを結合
        '''
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        '''
        x と y が同じグループか否か
        '''
        return self.find(x) == self.find(y)

    def get_size(self, x):
        '''
        x が属するグループの要素数
        '''
        x = self.find(x)
        return self.size[x]

N,M = II()
a,b = Line(M)

ans = 0
for i in range(M):
    uf = UF(N)
    for j in range(M):
        if j==i:
            continue
        else:
            uf.union(a[j]-1,b[j]-1)
    flag = False
    for k in range(N):
        for l in range(k+1,N):
            if not uf.is_same(k,l):
                flag = True
                break
        else:
            continue
        break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ABs = []
for i in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  ABs.append((a, b))
r = 0
for i in range(M):
  E = [[] for i in range(N)]
  for j in range(M):
    if j == i:
      continue
    a, b = ABs[j]
    E[a].append(b)
    E[b].append(a)
  V = [False]*N
  V[0] = True
  q = [0]
  while q:
    c = q.pop()
    ns = E[c]
    for n in ns:
      if not V[n]:
        V[n] = True
        q.append(n)
  if not all(V):
    r += 1
print(r)

Submission status: Accepted

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

A = []
B = []
graph = [[False for i in range(N)] for j in range(N)]
visited = [False for i in range(N)]

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

ans = 0

def dfs(v):
    visited[v] = True
    for v2 in range(N):
        if graph[v][v2]==False:
            continue
        if visited[v2]==True:
            continue
        dfs(v2)

for i in range(M):
    graph[A[i]][B[i]] = False
    graph[B[i]][A[i]] = False
    
    for j in range(N):
        visited[j] = False
               
    dfs(0)
    
    bridges = False
    
    for j in range(N):
        if visited[j]==False:
            bridges = True
            break
        
    if bridges:
        ans += 1
        
    graph[A[i]][B[i]] = True
    graph[B[i]][A[i]] = True

print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count


# その辺を抜いてUnionFindして親の数が2個以上なら count すればいい？

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

A = [0] * M
B = [0] * M

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

count = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        uf.unite(A[j], B[j])

    # 親の繋ぎ変え
    for i in range(N):
        uf.find(i)

#    print(uf.parent)

    if uf.get_parents() > 1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
ans=0
for x in edges:
    C=list(range(n))
    for y in edges:
        if y==x: continue
        C=[C[y[0]] if C[i]==C[y[1]] else C[i] for i in range(n)]
    if len(set(C))!=1: ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			return 0
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

	def size(self, x):
		return -self.root[self.find(x)]
		
n,m,*l = map(int,open(0).read().split())
edges = [(a,b) for a,b in zip(l[::2],l[1::2])]
ans = 0
for i in range(m):
	uf = UnionFind(n)
	for j in range(m):
		if i==j:
			continue
		else:
			a,b = edges[j]
			uf.unite(a,b)
	ans += uf.size(a)<n
print(ans)

Submission status: Accepted

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

class Node:
    def __init__(self, id_):
        self.id = id_
        self.link = []
        self.check = False
        

def main():
    N, M = map(int, input().split())
    
    nodes = [Node(i) for i in range(N+1)]

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

    for i in range(M):
        a, b = ab[i]
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    
    ans = 0
    for a, b in ab:
        check = [False] * (N+1)
        q = deque()
        tmp = 0
        q.append(nodes[1])
        check[1] = True
        while len(q) > 0:
            node = q.popleft()
            tmp += 1
            if node.id == a:
                ban_id = b
            elif node.id == b:
                ban_id = a
            else:
                ban_id = -1
            for nex in node.link:
                if nex.id != ban_id and not check[nex.id]:
                    check[nex.id] = True
                    q.append(nex)
        # print(a, b, tmp)
        if tmp != N:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[0 for _ in range(n)] for _ in range(n)]
lis_a = []
lis_b = []
for _ in range(m):
    a, b = map(int, input().split())
    lis_a.append(a-1)
    lis_b.append(b-1)
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1

def dfs(v):
    seen[v] = 1
    ret = 1
    for v2 in range(n):
        if g[v][v2] == 1 and seen[v2] == 0:
            dfs(v2)
    if seen == [1] * n:
        ret = 0
        
    return ret
ans = 0
for i in range(m):
    seen = [0] * n
    g[lis_a[i]][lis_b[i]] = 0
    g[lis_b[i]][lis_a[i]] = 0
    ans += dfs(0)
    g[lis_a[i]][lis_b[i]] = 1
    g[lis_b[i]][lis_a[i]] = 1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n,m=map(int,input().split())
    edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
    ans=0
    for x in edges:
        C=list(range(n))
        for y in edges:
            if y==x: continue
            C=[C[y[0]] if C[i]==C[y[1]] else C[i] for i in range(n)]
        if len(set(C))!=1: ans+=1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
#人のです。
N,M = map(int,input().split())
A = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    A[a-1][b-1]=1
    A[b-1][a-1]=1
#行き方が１通りしかない点から伸びた線を消し、新たに１通りになった点から線を消し、、、というループ（線の存在を１で表現）
flag = True
ans = 0
while(flag):
    flag = False
    for i in range(N):
        if A[i].count(1) == 1:
            flag = True
            ans += 1
            j = A[i].index(1)
            A[i][j] = 0
            A[j][i] = 0
print(ans)

Submission status: Accepted

Solution code:
#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)
input=stdin.readline

n,m=map(int,input().split())
graph=[[0]*n for _ in range(n)]
v=[list(map(int,input().split())) for _ in range(m)]
l=[0]*n

def dfs(x):
    if l[x]:
        return
    l[x]=1
    for i in range(n):
        if graph[x][i]:
            dfs(i)

for i in v:
    graph[i[0]-1][i[1]-1]=1
    graph[i[1]-1][i[0]-1]=1

ans=0
for i in range(m):
    graph[v[i][1]-1][v[i][0]-1]=0
    graph[v[i][0]-1][v[i][1]-1]=0

    chack=False
    l=[0]*n
    dfs(0)

    for j in l:
        if not j:
            ans+=1
            break
    graph[v[i][1]-1][v[i][0]-1]=1
    graph[v[i][0]-1][v[i][1]-1]=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    A[a-1][b-1]=1
    A[b-1][a-1]=1
flag = True
ans = 0
while(flag):
    flag = False
    for i in range(N):
        if A[i].count(1) == 1:
            flag = True
            ans += 1
            j = A[i].index(1)
            A[i][j] = 0
            A[j][i] = 0
print(ans)

Submission status: Accepted

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

def dfs(x):
    if Visited[x]: return
    Visited[x] = True
    for e in AB[x]:
        dfs(e)

n,m = map(int,input().split())
AB = [[] for i in range(n)]
Edges = [];
st = 0
for i in range(m):
    a,b = map(int,input().split())
    if i == 0: st = a-1
    AB[a-1].append(b-1)
    AB[b-1].append(a-1)
    Edges.append((a-1,b-1))
ans = 0
for a,b in Edges:
    AB[a].remove(b);AB[b].remove(a)
    Visited = [False] * n
    dfs(st)
    if not all(Visited):
        ans += 1
        #print(Visited)
    AB[a].append(b);AB[b].append(a)
print(ans)

Submission status: Accepted

Solution code:
import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()


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



n, m = na()
g = [[False] * n for i in range(n)]
li = []
for i in range(m):
    a, b = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = True
    li.append((a, b))

visit = [False] * n

ans = 0

for i in range(m):
    a, b = li[i]
    g[a][b] = g[b][a] = False
    for j in range(n):
        visit[j] = False
    dfs(0)
    flag = False
    for j in range(n):
        if not visit[j]:
            flag = True
    if flag:
        ans += 1
    g[a][b] = g[b][a] = True

print(ans)

Submission status: Accepted

Solution code:
def findunit(edges, N):
  roots = [i for i in range(N)]
  for edge in edges:
    if roots[edge[0]] == roots[edge[1]]:continue
    prv_root = roots[edge[1]]
    for idx, root in enumerate(roots):
      if root == prv_root:
        roots[idx] = roots[edge[0]]
  return roots

N,M=map(int,input().split())
edges = [ [int(a) -1 for a in input().split()] for _ in range(M)]
ans = 0
for i in range(M):
  if len(set(findunit(edges[:i] + edges[i+1:], N))) != 1:ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  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):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    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
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
  
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]
res = 0
for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if i == j:
      continue
    uf.Unite(A[j][0], A[j][1])
  for k in range(1, N + 1):
    if k != A[i][0] and k != A[i][1]:
      if uf.Count(k) != N:
        res += 1
      break
print(res)