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: Time Limit Exceeded

Solution code:
import numpy
N, M = map(int, input().split())
mat = [[0 for i in range(N)] for i in range(N)]
a = [0 for i in range(M)]
b = [0 for i in range(M)]
for i in range(M):
    st = input().split()
    a[i] = int(st[0])-1
    b[i] = int(st[1])-1
    mat[a[i]][b[i]]+=1
    mat[b[i]][a[i]]+=1

ans = 0
for n in range(M):
    mtx = numpy.array(mat)
    mtx[a[n],b[n]] -= 1
    mtx[b[n],a[n]] -= 1
    roopex = numpy.zeros([N, N])
    for i in range(N):
        for j in range(N):
            if mtx[i, j] != 0:
                roopex[i, j] = 1
    rootnum = numpy.dot(mtx, mtx)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if rootnum[i, j] != 0:
                    roopex[i, j] = 1
        rootnum = numpy.dot(rootnum, mtx)
    flag = 0
    for i in range(N):
        for j in range(N):
            if roopex[i, j] == 0:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
INF = 10**9
a = [[INF]*n for i in range(n)]
hen_m = []
for i in range(m):
    x1, x2 = map(int, input().split())
    x1 -= 1
    x2 -= 1
    hen_m.append([x1, x2])
    a[x1][x2] = 1
    a[x2][x1] = 1
for i in range(n):
    a[i][i] = 0

#ワーシャルフロイド
def warshall(n, c):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c[j][k] = min(c[j][k], c[j][i] + c[i][k])

ans = 0
# Mの辺を消して、わ～シャルフロイド
for i in range(m):
    b = [i[::] for i in a]
    x1 , x2 = hen_m[i]
    b[x1][x2] = INF
    b[x2][x1] = INF
    warshall(n, b)
    flag = 0
    for j in range(n - 1):
        for k in range(j + 1,n):
            if b[j][k] >= INF:
                flag = 1
                break
        if flag == 1:
            break
    #print(i, flag)
    ans += flag
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

class Graph:
    def __init__(self,node_num):
        self.adjacent = [ [] for i in range(node_num+1)]

    #エッジ群から隣接リストを作る
    def createAdjacent(self, edges):
        for edge in edges:
            self.adjacent[edge[0]].append(edge[1])
            self.adjacent[edge[1]].append(edge[0])

    def addEdge(self,edge):
        self.adjacent[edge[0]].append(edge[1])
        self.adjacent[edge[1]].append(edge[0])

    def deleteEdge(self,edge):
        self.adjacent[edge[0]].remove(edge[1])
        self.adjacent[edge[1]].remove(edge[0])


    #隣接リストの表示
    def printAdjacent(self):
        print(self.adjacent)

    #深さ優先で経路を探索
    def dfs(self,goal,cur_path,ans_pathes):
        n = cur_path[len(cur_path) - 1]
        if n == goal:
            ans_pathes.append(copy.deepcopy(cur_path))
        else:
            for x in self.adjacent[n]:
                if x not in cur_path:
                    cur_path.append(x)
                    self.dfs(goal,cur_path,ans_pathes)
                    cur_path.pop()

def main():
    #入力
    N, M = [int(i) for i in input().split()]
    edges = []
    for i in range(M):
        a,b = [int(i) for i in input().split()]
        edges.append([a,b])
    # print(edges)
    graph = Graph(N)
    graph.createAdjacent(edges)
    # graph.printAdjacent()
    bridge_cnt = 0
    for edge in edges:
        connected = True
        graph.deleteEdge(edge)
        for i in range(1,N+1):
            for j in range(1,N+1):
                path = []
                graph.dfs(j,[i],path)
                if(len(path)==0):
                    connected = False
                    break
        if not connected:
            #print(edge)
            bridge_cnt+=1
        graph.addEdge(edge)
    print(bridge_cnt)

if __name__ == '__main__':
    # input_init()
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

def set(adjacent,edge):
    for x in edge:
        adjacent[x[0]].append(x[1])
        adjacent[x[1]].append(x[0])

    
def search(goal,path):
    n = path[len(path) - 1]
    if n == goal:
        print(path)
    else:
        for x in adjacent[n]:
            if x not in path:
                path.append(x)
                search(goal, path)
                path.pop()

def search_loop_node(adjacent,start,path,node_loops):
    n = path[len(path)-1]
    for x in adjacent[n]:
        if x == start and len(path) >=2 and path[-2] != start :
            path.append(x)
            node_loops.append(copy.deepcopy(path))
            path.pop()
        elif x not in path:
            path.append(x)
            search_loop_node(adjacent,start, path,node_loops)
            path.pop()

def main():
    #入力
    N, M = [int(i) for i in input().split()]
    edge = []
    for i in range(M):
        a,b = [int(i) for i in input().split()]
        edge.append([a,b])

    #辺の生成
    adjacent=[ [] for i in range(N+1)]
    loops=[]
    set(adjacent,edge)
    #ループの検索
    for i in range(N):
        search_loop_node(adjacent,i,[i],loops)
    #ループに属する辺(橋でない辺)の検索
    not_bridge = []
    for loop in loops:
        pre_node = loop[0]
        for node in loop:
            if pre_node < node and [pre_node, node] not in not_bridge:
                not_bridge.append([pre_node,node])
            pre_node = node
    #答えは全体の辺の数からループでないものを引いた数
    print(M-len(not_bridge))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def reachable(lines, through, a, b):
    if a == b:
        return True
    lines = lines[:]
    lines.remove(through)
    for line in lines:
        if b in line and reachable(lines, line, a, line[line.index(b) - 1]):
            return True
    return False

N, M = map(int, input().split())
lines = [input().split() for _ in range(M)]
print(M - sum(reachable(lines, line, *line) for line in lines))

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
import copy

n, m = map(int, input().split())

lis = [[10000000 for i in range(n)] for j in range(n)]
hen = []
for _ in range(m):
    hen.append(list(map(int, input().split())))

ans = 0
for x in range(m):
    lis_tmp = copy.deepcopy(lis)
    bri = copy.deepcopy(hen)
    bri.pop(x)
    for y in range(m-1):
        lis_tmp[bri[y][0]-1][bri[y][1]-1] = 1
        lis_tmp[bri[y][1]-1][bri[y][0]-1] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                lis_tmp[i][j] = min(lis_tmp[i][j], lis_tmp[i][k] + lis_tmp[k][j])

    if 10000000 in list(chain.from_iterable(lis_tmp)):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

n, m = map(int, input().split())

lis_raw = [[10000000 for i in range(n)] for j in range(n)]
lis = np.array(lis_raw)
hen = []
for _ in range(m):
    hen.append(list(map(int, input().split())))

ans = 0
for x in range(m):
    lis_tmp = copy.deepcopy(lis)
    bri = copy.deepcopy(hen)
    bri.pop(x)
    for y in range(m-1):
        lis_tmp[bri[y][0]-1][bri[y][1]-1] = 1
        lis_tmp[bri[y][1]-1][bri[y][0]-1] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                lis_tmp[i][j] = min(lis_tmp[i][j], lis_tmp[i][k] + lis_tmp[k][j])

    if 10000000 in lis_tmp:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = 0
for i in range(M):
  C = set()
  D = set()
  count = 0
  boo = True
  while(boo):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j])
          C.add(b[j])
          count += 1
        if C <= {a[j]} or C <= {b[j]}:
          C.add(a[j])
          C.add(b[j])
    if(C in D):
      boo = False
      break
    else:
      D = C
  if(len(C) == N):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = 0
C = set()
D = set()
for i in range(M):
  count = 0
  boo = True
  while(boo):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j])
          C.add(b[j])
          count += 1
        if C <= {a[j]} or C <= {b[j]}:
          C.add(a[j])
          C.add(b[j])
    if(C in D):
      boo = False
      break
    else:
      D = C
  if(len(C) == N):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = 0
C = set()
D = set()
for i in range(M):
  count = 0
  boo = True
  while(boo):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j])
          C.add(b[j])
          count += 1
        if C <= {a[j]} or C <= {b[j]}:
          C.add(a[j])
          C.add(b[j])
    if(D in C):
      boo = False
      break
    else:
      D = C
  if(len(C) == N):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# Union Find
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # x < y にする
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# 根の個数を返す
def group_count():
    return sum(x < 0 for x in par)


n, m = map(int, input().split())
l = []
for _ in range(m):
    l.append(tuple(map(int, input().split())))

ans = 0
for j in range(m):
    par = [-1] * n
    for i, ab in enumerate(l):
        if i != j:
            unite(ab[0] - 1, ab[1] - 1)
    if group_count() == 2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):#要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):#要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):#要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]
 
    def same(self, x, y):#要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)
 
    def members(self, x):#要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):#すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):#グループの数を返す
        return len(self.roots())
 
    def all_group_members(self):#{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):#print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = map(int,input().split())

ab = []
for _ in range(m):
    a, b = map(int,input().split())
    ab.append((a-1, b-1))
    
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, r in enumerate(ab):
        if j == i:
            continue
        a, b = r
        uf.union(a, b)
    if uf.group_count() > 1:
        ans += 1
        
print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
            uf.union(a[j][0]-1, a[j][1]-1)
    if uf.size(0) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def is_bridge(n, pi, to_info):
	is_a=[-1]*n
	q =collections.deque()
	q.append(0)
	#ex = [p[0]-1, p[1] - 1]
	while q:
		pos = q.popleft()
		for to in to_info[pos]:
			if pos in pi and to in pi:
				continue
			if is_a[to] != -1:
				continue
			is_a[to]=1
			q.append(to)
	
	return min(is_a) == -1


def main():
	#a = int(input())
	n, m = tin()
	#s = input()
	path = []
	to_info = [[] for _ in range(n)]
	for _ in range(m):
		a, b = tin()
		path.append([a-1, b-1])
		to_info[a-1].append(b-1)
		to_info[b-1].append(a-1)
		
	ret = 0
	#pa(path)
	for pi in path:
		if is_bridge(n, pi, to_info):
			#pa(pi)
			ret += 1
	print(ret)
	
	
#+++++
isTest=False

def pa(*vl):
	if not isTest:
		return
	for v in vl:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
n,m=map(int,input().split())
uf=UnionFind(n)
l=[]
ans=0
for i in range(m):
  a,b=map(int,input().split())
  l.append([a,b])
for i in range(m):
  for j in range(m):
    if i!=j:
      uf.union(l[j][0]-1,l[j][1]-1)
  if uf.group_count()!=1:
    ans+=1
  uf.__init__(n)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1 for i in range(n)]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]

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

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

N, M = map(int, input().split())
AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    un = UnionFind(N)
    for j in range(M):
        if i != j:
            un.unite(AB[j][0], AB[j][1])
    if un.count(0) != N:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(m):
    a, b = list(map(int, input().split()))

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

ind = 1
queue = [0]
visitedOrder = {}
visited = {}
cnt = 0

while queue:
    cur = queue[-1]

    if cur not in visited:
        visited[cur] = ind
        visitedOrder[cur] = ind
        ind += 1

    neighbours = False
    for nei in edges[cur]:
        if nei not in visited:
            neighbours = True
            queue.append(nei)
            break

    if not neighbours:
        queue.pop()

        if cur != 0:
            connected = visited[cur]

            for nei in edges[cur]:
                if nei != queue[-1]:
                    connected = min(connected, visited[nei])

            visited[cur] = connected
            if connected > visitedOrder[queue[-1]]:
                cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = [[] for _ in range(N)]
H = []
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  G[a].append([b,i]);G[b].append([a,i]) #iを辺のIDとして保存
  H.append([a,b])
ans = 0
 
def dfs(v,ID): #IDの辺を使えない
  visited.add(v)
  for u,idx in G[v]:
    if idx == ID or u in visited:
      continue
    dfs(u,ID)
 
for i in range(M):
  visited = set([])
  start = H[i][0]
  goal = H[i][1]
  dfs(start,i)
  if goal not in visited:
    ans +=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
reach = [0]*(n+1)
l = [[] for i in range(n+1)]
for i in range(m):
  a,b = map(int, input().split())
  l[a].append(b)
  l[b].append(a)
  
def dfs(s, parent):
  reach[s] = 1
  for i in l[s]:
    if i == parent: continue
    if reach[i] == 0:
      dfs(i, s)
    else:
      reach[i] += 1

loop = [0]*(n+1)
for i in range(1, n+1):
  reach = [0]*(n+1)
  dfs(i, 0)
  if reach[i] != 1:
    loop[i] = 1
ans = 0
for i in range(1, n+1):
  for j in l[i]:
    if loop[i] == 1 and loop[j] == 1:
      ans += 1
print(m - ans//2)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


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


def dfs(G, i):
    seen = set([i])
    stack = [i]
    cnt = 0
    while stack:
        node = stack.pop()
        cnt += 1
        for _n in G[node]:
            if _n not in seen:
                seen.add(_n)
                stack.append(_n)
    return cnt


def main():
    from collections import defaultdict
    G = defaultdict(set)
    edge = []
    n, m = input_int_list()

    for _ in range(m):
        a, b = input_int_list()
        G[a].add(b)
        G[b].add(a)
        edge.append((a, b))

    ans = 0
    # すべての辺を取り除いたときに、dfsで全ノードを辿れるか調べる
    # O(n*m)
    for a, b in edge:
        G[a].remove(b)
        G[b].remove(a)
        cnt = dfs(G, 1)
        if cnt < n:
            ans += 1
        G[a].add(b)
        G[b].add(a)

    print(ans)

    return


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

N,M = map(int, input().split())
ab_s = [list(map(int, input().split())) for _ in range(M)]
answer = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        a,b = map(int, ab_s[j])
        uf.Unite(a,b)
    a,b = map(int, ab_s[i])
    if not uf.isSameGroup(a,b):
        answer += 1
print(answer)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

cnt = 0
for i in range(M):
  uf = UnionFind(N+1)
  for a, b in [*ABS[:i], *ABS[i+1:]]:
    uf.union(a, b)
  if uf.group_count() > 2:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

"""
https://note.nkmk.me/python-union-find/
素集合データ構造

:parameter
union(x, y): 2つの集合を一つに併合する
find(x): xがどの集合に属しているかを判定する
size(x): 要素xが属するグループのサイズ（要素数）を返す
same(x, y): 要素x, yが同じグループに属するかどうかを返す
members(x): 要素xが属するグループに属する要素をリストで返す
roots(): 全ての根の要素をリストで返す
group_count(): グループの数を返す
all_group_members(): 辞書を返す。　key = ルート要素, value = そのグループに含まれる要素のリスト
__str__(): print()での表示用。ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
"""
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def all_group_count(self):
        return [self.size(r) for r in self.roots()]

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N, M = MI()
    E = []
    for i in range(M):
        a, b = MI1()
        E.append((a, b))

    ans = 0
    for a, b in E:
        uf = UnionFind(N)
        for v1, v2 in E:
            if (v1, v2) == (a, b):
                continue
            uf.union(v1, v2)
        # print(uf.group_count())
        if uf.group_count() > 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, M = MI()
    V = [[] for _ in range(N)]
    E = []
    for i in range(M):
        a, b = MI1()
        V[a].append(b)
        V[b].append(a)
        E.append((a, b))

    ans = 0
    for a, b in E:
        used = [0] * N
        flag = True
        q = deque([a])
        used[a] = 1
        while q:
            cur = q.popleft()

            for nv in V[cur]:
                if (a, b) == (cur, nv) or (a, b) == (nv, cur):
                    continue

                if used[nv]:
                    continue

                if nv == b:
                    flag = False
                    q = []
                    break

                q.append(nv)
                used[nv] = 1
            # print(a, b, q)

        if flag:
            ans += 1
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

def bfs(i):
  dist = [-1] * n
  dist[i] = 0
  d = deque()
  d.append(i)
  while d:
    v = d.popleft()
    for j in graph[v]:
      if dist[j] != -1:
        continue
      dist[j] = dist[v] + 1
      d.append(j)
  return dist

def judge(c):
  graph[c[0]].remove(c[1])
  graph[c[1]].remove(c[0])
  dist = bfs(0)
  graph[c[0]].append(c[1])
  graph[c[1]].append(c[0])
  for d in dist:
    if d == -1:
      return True
  return False

ans = 0
for c in cand:
  if judge(c):
    ans += 1
print(ans)