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: Wrong Answer

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

edges = {}
node_count = 0
node_seen = set()
edge_list = []


def dfs(t_node, t_edge):
    global node_count, node_seen
    node_count += 1
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if t_node in edge_list[t_edge] and nextn in edge_list[t_edge]:
                continue
            else:
                dfs(nextn, t_edge)

def main():
    global edges, node_count, node_seen, edge_list
    n, m = map(int, input().split())
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
        edge_list.append((g, s))
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(1, itry)
        r += node_count < n
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

edges = {}
node_count = 0
node_seen = set()
edge_list = []


def dfs(t_node, t_edge):
    global node_count, node_seen
    node_count += 1
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if (t_node, nextn) == edge_list[t_edge] or (nextn, t_node) == edge_list[t_edge]:
                continue
            else:
                dfs(nextn, t_edge)

def main():
    global edges, node_count, node_seen, edge_list
    n, m = map(int, input().split())
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
        edge_list.append((g, s))
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(1, itry)
        r += node_count < n
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

edges = {}
node_count = 0
node_seen = set()
edge_list = []
def dfs(t_node, t_edge):
    global node_count, node_seen
    node_seen.add(t_node)
    next_nodes = set(edges[t_node]) - node_seen
    node_count += 1
    if len(next_nodes) == 0:
        return
    else:
        for nextn in next_nodes:
            if (t_node, nextn) != edge_list[t_edge] and (nextn, t_node) != edge_list[t_edge]:
                dfs(nextn, t_edge)

def main():
    global edges, node_count,node_seen,edge_list
    n, m = map(int, input().split())
    edges = {e: [] for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].append(g)
        edges[g].append(s)
        edge_list.append((s, g))
        edge_list.append((g, s))
    r = 0
    for itry in range(m):
        node_seen = set()
        node_count = 0
        dfs(1, itry)
        r += node_count < n
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def dfs(x,y,tmp):
  tmp+=[x,y]
  del test[test.index([x,y])]
  for j in test:
    if j[0]==y or j[1]==y or j[0]==x or j[1]==x:
      nx=j[0]
      ny=j[1]
      dfs(nx,ny,tmp)



#試しに1箇所切って繋がれるか試していく
cnt=0
for i in range(m):
  test=ab[:i]+ab[i+1:]
  tmp=[]
  dfs(test[0][0],test[0][1],tmp)
  tmp=set(tmp)
  if len(tmp)==n:
    cnt+=1
print(m-cnt)

Submission status: Wrong Answer

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

def dfs(x,y,tmp):
  tmp+=[x,y]
  del test[test.index([x,y])]
  for j in test:
    if j[0]==y or j[1]==y or j[0]==x or j[1]==x:
      nx=j[0]
      ny=j[1]
      dfs(nx,ny,tmp)



#試しに1箇所切って繋がれるか試していく
cnt=0
for i in range(m):
  test=ab[:i]+ab[i+1:]
  tmp=[]
  dfs(test[0][0],test[0][1],tmp)
  tmp=set(tmp)
  if len(tmp)<n:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

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

def dfs(x,y,tmp):
  tmp+=[x,y]
  del test[test.index([x,y])]
  for j in range(len(test)):
    if len(test)==0 or j>=len(test):
      break
    if test[j][0]==y or test[j][1]==y or test[j][0]==x or test[j][1]==x:
      nx=test[j][0]
      ny=test[j][1]
      dfs(nx,ny,tmp)


#試しに1箇所切って繋がれるか試していく
cnt=0
for i in range(m):
  test=ab[:i]+ab[i+1:]
  tmp=[]
  dfs(test[0][0],test[0][1],tmp)
  tmp=set(tmp)
  if len(tmp)<n:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(10**5)

def search(v, g, seen, disc, low, parent, step, cnt):
	seen[v] = True
	step += 1
	disc[v] = low[v] = step
	n_cnt = cnt
	for i in g[v]:
		if not seen[i]:
			parent[i] = v
			n_cnt = search(i, g, seen, disc, low, parent, step, cnt)
			low[v] = min(low[i], low[v])
			if low[i] > disc[v]:
				n_cnt += 1
		elif i != parent[v]:
			low[v] = min(low[i], disc[i])
	return n_cnt

def resolve():
	n, m = map(int, input().split())
	g = [[] for _ in range(n)]
	seen = [None] * n
	disc = [None]*n
	low = [None]*n
	parent = [None]*n
	for _ in range(m):
		a, b = map(int, input().split())
		g[a-1].append(b-1)
		g[b-1].append(a-1)
	cnt = search(0, g, seen, disc, low, parent, 0, 0)
	print(cnt)
resolve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True

class UnionFind(object):
    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()),


def main():
    N, M = MI()
    a = [0] * M
    b = [0] * M
    ans = 0

    for i in range(M):
        _a, _b = MI()
        a[i], b[i] = _a - 1, _b - 1

    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if i == j:
                print(a[j], b[j])
                continue
            uf.union(a[j], b[j])
        if len(uf.roots()) != 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


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


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.parent = [i for i in range(n_nodes)]
        self.rank = [1] * n_nodes
        self.size = [1] * n_nodes

    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[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


def main():
    N, M = map(int, input().split())
    Tree = UnionFind(N)
    cnt = 0
    for _ in range(M):
        A, B = map(int, input().split())
        if Tree.check(A - 1, B - 1):
            cnt -= 2
        else:
            Tree.unite(A - 1, B - 1)
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

cnt = 0
for i in range(N):
    par = list(range(N + 1))
    rank = [0] * (N + 1)
    for j, (u, v) in enumerate(X):
        if i == j:
            continue
        unite(u, v)
    
    res = True
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            res &= find(j) == find(k)

    cnt += int(not res)
        
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
class Node:
    def __init__(self):
        self.adjacent=[]

x,y=map(int,input().split())
nodelist=[Node() for s in range(x)]
for a in range(y):
    b,c=map(int,input().split())
    nodelist[b-1].adjacent.append(c-1)
    nodelist[c-1].adjacent.append(b-1)
count=0
nqueue=deque()
nqueue.append(0)
vqueue=deque()
vqueue.append(0)
while True:
    l=[]
    for t in range(len(nqueue)):
        l.append(nqueue.popleft())

    for a in l:
        for g in nodelist[a].adjacent:
            if not g in vqueue:
                nqueue.append(g)
                vqueue.append(g)
    count+=1
    if len(vqueue)==x:
        break

print(count-(x-1-count))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

abm = [None] * m
for i in range(m):
    abm[i] = list(map(int, input().split(' ')))

def check(i):
    cl = [False] * n
    edges = abm[:i] + abm[i + 1:]
    d = deque([1])

    def bfs():
        while True:
            if not d:
                return
            
            v = d.popleft()
            if cl[v - 1]:
                continue
            else:
                cl[v - 1] = True

                nxts = [edge[0] for edge in edges if edge[1] == v]
                for nxt in nxts:
                    d.append(nxt)

                nxts = [edge[1] for edge in edges if edge[0] == v]
                for nxt in nxts:
                    d.append(nxt)

    bfs()

    if cl.count(False):
        return True
    else:
        return False

count = 0
for i in range(n):
    if check(i):
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
X=[]
M=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a,b])
    M[a-1].append(b-1)
    M[b-1].append(a-1)
ans=0
for i in range(m):
    se={X[i][0],X[i][1]}
    q=deque([0])
    visited=[0]*n
    while q:
        s=q.popleft()
        if visited[s]==1:
            continue
        visited[s]=1
        for x in M[s]:
            if {s,x}!=se:
                q.append(x)
    if sum(visited)!=n:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
ans = 0
for i in s:
    l = list(range(n))
    for j in s:
        if i!=j:
            for k in range(n):
                if l[k]==l[j[1]-1]: l[k]=l[j[0]-1]
    if len(set(l))!=1: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
ans = 0
for i in s:
    l = list(range(n))
    for j in s:
        if i!=j:
            for k in range(n):
                if l[k]==l[j[1]-1]:
                    l[k]=l[j[0]-1]
    if len(set(l))!=1: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
icase=0
if icase==0:
    n,m=map(int, input().split())
    a=[]
    b=[]
    for i in range(m):
        ai,bi=map(int, input().split())
        a.append(ai)
        b.append(bi)
elif icase==1:
    n=6
    m=5
#    a=[[1],[2],[3],[4],[5]]
#    b=[[2],[3],[4],[5],[6]]
    a=[1,2,3,4,5]
    b=[2,3,4,5,6]
elif icase==2:
    n=7
    m=7
    a=[1,2,3,4,4,5,6]
    b=[3,7,4,5,6,6,7]

    
vtx=[]
for i in range(n):
    vtx.append([i+1])
icnt=0

for j in range(m):    
    vtx1=vtx.copy()
    a1=a.copy()
    b1=b.copy()
    del a1[j]
    del b1[j]
    
    for i in range(m-1):
        for v1 in vtx1:
            if a1[i] in v1:
                for v2 in vtx1:
                    if v1!=v2:
                        if b1[i] in v2:
                            break
                if v1!=v2:
                    vtx1.remove(v1)
                    vtx1.remove(v2)
                    v3=v1+v2
                    vtx1.append(v3)
#        print(a[i],b[i],len(vtx1),vtx1)
#    print(len(vtx1),vtx1)
    if len(vtx1)!=1:
        icnt=icnt+1
print(icnt)        
#for i in range(m):
#    for v1 in vtx1:
#        if a[i] in v1:
#            for v2 in vtx1:
#                if v1!=v2:
#                    if b[i] in v2:
#                        break
#            if v1!=v2:
#                vtx1.remove(v1)
#                vtx1.remove(v2)
#                v3=v1+v2
#                vtx1.append(v3)
#    print(a[i],b[i],len(vtx1),vtx1)

Submission status: Wrong Answer

Solution code:
import copy
def is_linking(sides):
    side = copy.copy(sides.pop())
    flag = True
    while flag:
        if not sides:
            if len(side) == n:
                return True
            else:
                return False
        for i in range(len(sides)):
            if side & sides[i]:
                side |= sides.pop(i)
                print(side)
                break
            elif i == len(sides) - 1:
                flag = False
    if len(side) == n:
        return True
    else:
        return False       
    
n, m = map(int, input().split())
all_sides = [set(input().split()) for _ in range(m)]
count = 0
for i in range(m):
    sides = all_sides[:i] + all_sides[i+1:]
    if is_linking(sides):
        continue
    else:
        count += 1
print(count)

Submission status: Wrong Answer

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())
ab = [list(map(int,input().split())) for _ in range(m)]

ans = 0

for i in range(n):
    ab2 = ab[:i] + ab[i+1:]
    uf = UnionFind(n)
    for a,b in ab2:
        uf.union(a-1,b-1)
    if uf.group_count() > 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
edges = defaultdict(list)
N,M = map(int, input().split())
for i in range(M):
    a,b  = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

# 葉から切っていって、次数が1のところを切る
# 葉の探索
leaf = []
q = deque()
cnt = 0
for i in range(N):
    if len(edges[i]) == 1:
        q.append(edges[i][0])
        leaf.append(i)
        cnt += 1

# print(edges)
# print(leaf)
# print(list(q))

while len(q) > 0:
    i = q.pop()
    nx = edges[i]
    if len(nx) == 2:
        leaf.append(i)
        for j in nx:
            if j not in leaf:
                # print(i,nx,j,leaf)
                q.append(j)
                cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
edges = defaultdict(list)
N,M = map(int, input().split())
for i in range(M):
    a,b  = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

# 葉から切っていって、次数が1のところを切るという感じかね
# 葉の探索
leaf = []
q = deque()
cnt = 0
for i in range(N):
    if len(edges[i]) == 1:
        q.append(edges[i][0])
        leaf.append(i)
        cnt += 1

# print(edges)
# print(leaf)
# print(list(q))

while len(q) > 0:
    i = q.popleft()
    nx = edges[i]
    if len(nx) == 2:
        leaf.append(i)
        for j in nx:
            if j not in leaf:
                q.append(j)
                cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
edges = defaultdict(list)
N,M = map(int, input().split())
for i in range(M):
    a,b  = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
# 葉から切っていって、次数が1のところを切るという感じかね
# 葉の探索
leaf = []
q = deque()
cnt = 0
for i in range(N):
    if len(edges[i]) == 1:
        q.append(edges[i][0])
        leaf.append(i)
        cnt += 1

# print(edges)
# print(leaf)
# print(list(q))

while len(q) > 0:
    i = q.popleft()
    nx = edges[i]
    if len(nx) == 2:
        for j in nx:
            if j not in leaf:
                # print(i,nx,j,leaf)
                leaf.append(i)
                q.append(j)
                cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
def dfs(graph,visited,initial):
    global cnt 
    visited[initial] = 1
    all_visited = True
    for i in visited:
        if i == 0:
            all_visited = False
    
    if all_visited == True:
        cnt = 1
    
    for i in range(len(graph)):
        if graph[initial][i] == 1:
            if visited[i] == 0:
                dfs(graph , visited , i)
                visited[i] = 0


n,m = map(int,input().split()) 
graph = [[0 for i in range(n)]for j in range(n)]
m_list = []
for i in range(m):
    a,b = map(int,input().split()) 
    m_list.append([a,b])
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
    
    
bridge = 0
for i in m_list:
    visited = [0]*n
    graph_tmp= graph
    graph_tmp[i[0]-1][i[1]-1] = 0
    graph_tmp[i[1]-1][i[0]-1] = 0
    cnt = 0
    dfs(graph_tmp , visited,0)
    if cnt == 0:
        bridge += 1
        
print(bridge)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = {}
tr = lambda x: 3 * x - (x - 1)
for _ in range(m):
    a_, b_ = map(int, input().split())
    if a_ not in ab.keys():
        ab[a_] = []
    ab[a_].append(b_)
for ab_val in ab.values():
    if len(ab_val) == 1:
        continue
    else:
        cnt = 0
        for val in ab_val:
            if val not in ab.keys():
                continue
            else:
                for v in ab[val]:
                    if v in ab_val:
                        cnt += 1
        m -= tr(cnt)
print(m)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
cnt = 0
def solve():
    def lowlink(v):
        global cnt
        def dfs(x):
            global cnt
            for y in v[x]:
                if pre[y] is None:
                    cnt += 1
                    pre[y] = low[y] = cnt
                    py = dfs(y)
                    if py < low[x]:
                        low[x] = py
                else:
                    if pre[y]+1 < low[x]:
                        low[x] = pre[y]
                if pre[x] < low[y]:
                    res.append((x,y))
            return low[x]

        pre = [None]*n
        low = [None]*n
        res = []
        for x in range(n):
            if pre[x] is None:
                pre[x] = low[x] = cnt
                dfs(x)
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    ans = lowlink(v)
    print(len(ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
cnt = 0
def solve():
    def lowlink(v):
        global cnt
        def dfs(x):
            global cnt
            for y in v[x]:
                if pre[y] is None:
                    cnt += 1
                    pre[y] = low[y] = cnt
                    py = dfs(y)
                    if py < low[x]:
                        low[x] = py
                else:
                    if pre[y]+1 < low[x]:
                        low[x] = pre[y]
                if pre[x] < low[y]:
                    res.append((x,y))
            return low[x]

        pre = [None]*n
        low = [None]*n
        pre[0] = low[0] = 0
        res = []
        dfs(0)
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    ans = lowlink(v)
    print(len(ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

def sample():
    uf = UnionFind(6)
    print(uf.parents)
    uf.union(0, 2)
    print(uf.parents)
    uf.union(1, 3)
    print(uf.parents)
    uf.union(4, 5)
    print(uf.parents)

def atc001():
    n, q = map(int, input().split())
    uf = UnionFind(n)
    for i in range(q):
        p, a, b = map(int, input().split())
        if p == 0:
            uf.union(a, b)
        else:
            if uf.same(a, b):
                print("Yes")
            else:
                print("No")

def abc049():
    n, k, l = map(int, input().split())
    road = UnionFind(n)
    train = UnionFind(n)
    for i in range(k):
        p, q = map(int, input().split())
        road.union(p - 1, q - 1)
    for i in range(l):
        p, q = map(int, input().split())
        train.union(p - 1, q - 1)

    pair = []
    pair_cnt = {}
    for i in range(n):
        t, r = road.find(i), train.find(i)
        pair.append([t, r])
        key = t * (10 ** 6) + r
        if key in pair_cnt:
            pair_cnt[key] += 1
        else:
            pair_cnt[key] = 1

    for i in range(n):
        [t, r] = pair[i]
        key = t * (10 ** 6) + r
        print(pair_cnt[key], end = " ")

def arc097():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    pair = UnionFind(n)
    for i in range(m):
        x, y = map(int, input().split())
        pair.union(x - 1, y - 1)

    cnt = 0
    for i in range(n):
        if pair.same(i, p[i] - 1):
            cnt += 1
    print(cnt)

def arc032():
    n, m = map(int, input().split())
    road = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        road.union(a - 1, b - 1)

    print(road.group_count() - 1)

def abc075():
    n, m = map(int, input().split())
    input_list = [list(map(int, input().split())) for _ in range(m)]
    cnt = 0
    for i in range(n):
        road = UnionFind(n)
        for j in range(m):
            if i != j:
                road.union(input_list[j][0] - 1, input_list[j][1] - 1)
        if road.group_count() >= 2:
            cnt += 1

    print(cnt)
abc075()

Submission status: Wrong Answer

Solution code:
n , m = map(int, input().split())
combis = [set(list(map(int, input().split()))) for i in range(m)]
count = 0
for i in range(m):
    combis_x = combis[0:i] + combis[i+1:m]
    islands = []
    for combi in combis_x:
        # init
        if not islands:
            islands.append(combi)
            continue
        # compare existed islands
        new_islands = islands
        joint_i = []
        for j, island in enumerate(islands):
            if not island.isdisjoint(combi):
                new_islands[j] = island | combi
                joint_i.append(j)
        else:
            if not joint_i:
                new_islands.append(combi)
            elif len(joint_i) == 2:
                new_islands[joint_i[0]] = new_islands[joint_i[0]] | new_islands[joint_i[1]]
                new_islands.pop(joint_i[1])
        islands = new_islands

    # judge
    if len(islands) == 1 and len(islands[0]) == n:
        continue
    elif len(islands) == 1 and len(islands[0]) == n - 1:
        count += 1
    else:# len(islands) == 2 and islands[0].isdisjoint(islands[1]):
        count += 1
print("count", count)

Submission status: Wrong Answer

Solution code:
def main():
    vertex, edge_num = map(int, input().split())
    edge = [[] for _ in range(vertex)]
    all_edge = []
    for _ in range(edge_num):
        all_edge.append(tuple(map(lambda x: int(x) - 1, input().split())))
        edge[all_edge[-1][0]].append(all_edge[-1][1])
        edge[all_edge[-1][1]].append(all_edge[-1][0])

    def search(exception):
        next_search = [0]
        has_searched = []
        result = 0
        while not next_search == []:
            now = next_search.pop(0)
            for d in edge[now]:
                if d in exception and now in exception:
                    continue
                elif d not in has_searched:
                    has_searched.append(now)
                    next_search.append(d)
                    result += 1
        return result == vertex - 1

    answer = 0
    for ex in all_edge:
        if not search(ex):
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()