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:
N,M=map(int,input().split(' '))
R=[list(map(int,input().split(' '))) for i in range(M)]
Mat=[[0]*N]*N
for r in R:
	Mat[r[0]-1][r[1]-1]=1

stack=[1]
island=[]

ans=0
Matmini=[]

def dfs():
	global stack
	global island
	global Matmini
	if stack==[]:
		return None
	if len(set(island))==N:
		#全頂点が網羅できていたらそこで終了
		return None
	else:
		#たどれるノードがあるかどうかを確認
		for i in range(2,N+1):
			#iが未訪問のときのみ処理続行
			if i not in stack:
				#実際に辺が存在するか
				if Matmini[stack[0]-1][i-1]==1:
					stack = [i] + stack
					dfs()
		#これ以上先に進めなくなったら島の構成要素を更新
		island += stack
		stack.pop(0)

for r in R:
	#Rからi番目の辺だけ除去したもの
	Matmini = Mat[:]
	Matmini[r[0]-1][r[1]-1]=0
	stack = [1]
	island = []
	dfs()
	if len(set(island))!=N:
		ans += 1
		
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split(' '))
R=[list(map(int,input().split(' '))) for i in range(M)]
Mat=[[0]*N]*N
for r in R:
	Mat[r[0]-1][r[1]-1]=1
	Mat[r[1]-1][r[0]-1]=1

stack=[1]
island=[]

ans=0
Matmini=[]

def dfs():
	global stack
	global island
	global Matmini
	if stack==[]:
		return None
	if len(set(island))==N:
		#全頂点が網羅できていたらそこで終了
		return None
	else:
		#たどれるノードがあるかどうかを確認
		for i in range(1,N+1):
			#iが未訪問のときのみ処理続行
			if i not in stack:
				#実際に辺が存在するか
				if Matmini[stack[0]-1][i-1]==1:
					stack = [i] + stack
					dfs()
		#これ以上先に進めなくなったら島の構成要素を更新
		island += stack
		stack.pop(0)

for r in R:
	#Rからi番目の辺だけ除去したもの
	Matmini = Mat
	Matmini[r[0]-1][r[1]-1]=0
	Matmini[r[1]-1][r[0]-1]=0
	stack = [1]
	island = []
	dfs()
	if len(set(island))!=N:
		ans += 1
		
print(ans)

Submission status: Wrong Answer

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

graph = [[] for i in range(N)]

for i in range(M):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    graph[ai].append(bi)
    graph[bi].append(ai)

low = [N] * N
visited = [False] * N


def dfs(k, pos, parent):
    low[pos] = k

    k += 1

    visited[pos] = True

    for i in graph[pos]:
        if not visited[i]:
            dfs(k, i, pos)
            low[pos] = min(low[pos], low[i])
        elif i != parent:
            low[pos] = min(low[pos], low[i])


def main():
    dfs(0, 0, -1)

    ans = 0

    for i in range(N):
        for j in graph[i]:
            if low[j] < low[i]:
                ans += 1

    print(ans)
    return


main()

Submission status: Wrong Answer

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

node = {}
for i in range(1, n+1):
	node[i] = [y[abs(y.index(i)-1)] for y in [x for x in pairs if i in x]]

ans = 0
def search_node(a, b):
	global ans
	if len(node[a]) == 2:
		ans += 1
		search_node(node[a][abs(node[a].index(b)-1)], a)
	else:
		ans += 1

for j in range(1, n+1):
	if len(node[j]) == 1:
		search_node(node[j][0], j)
	else:
		pass

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    self.n   = num
    self.size = [1]*num

#親を探す
  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]: #ランクの高い方に基準を合わせる
      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]
    self.size[y] = 0

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

  def all_find(self):
    for n in range(len(self.par)):
      self.find(n)


n,m=map(int,input().split())
edges=[[0]*n for i in range(n)]
uf=UnionFind(n)
ans=0
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append([a,b])
  uf.union(a-1,b-1)
for i in range(m):
  uf1=UnionFind(n)
  for j in range(m):
    a,b=ab[j]
    if i==j:
      continue
    uf1.union(a-1,b-1)
  if all([True if i==j else False for i,j in zip(uf.par,uf1.par)])!=True:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    self.n   = num
    self.size = [1]*num

#親を探す
  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]: #ランクの高い方に基準を合わせる
      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]
    self.size[y] = 0

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

  def all_find(self):
    for n in range(len(self.par)):
      self.find(n)


n,m=map(int,input().split())
edges=[[0]*n for i in range(n)]
uf=UnionFind(n)
ans=0
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append([a,b])
  uf.union(a-1,b-1)
for i in range(m):
  uf1=UnionFind(n)
  for j in range(m):
    a,b=ab[j]
    if i==j:
      continue
    uf1.union(a-1,b-1)
  if sum([abs(i-j) for i,j in zip(uf.par,uf1.par)])!=0:
    ans+=1
print(ans)

# 1-3-4-5-6 7-2

Submission status: Wrong Answer

Solution code:
# UnionFind構造

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]

count = 0
for i in range(len(lst)):
    llst = lst[:]
    del llst[i]
    a = UnionFind(n)
    for i in llst:
        a.union(i[0], i[1])
    rootset = set()
    for i in range(1, n):
        rootset.add(a.find(i))
    if len(rootset)==1:
        pass
    else:
        count += 1
        
print(count)

Submission status: Wrong Answer

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

def main():
	p, l = map(int, input().split(" "))
	
	lines = []
	for i in range(l):
		line = input().split(" ")
		tmp = [int(s) for s in line]
		lines.append(tmp)
		
	result = 0
	peeks = run(lines)
	for i, line in enumerate(lines):
		a = peeks[str(line[0])]
		b = peeks[str(line[1])]
		flg = False
		for aa in a:
			if aa in b:
				flg = True
				break
		
		if flg == False:
			result = result + 1
		
	print(result)
		
def run(lines):
	peeks = {}
	for i, line in enumerate(lines):
		if str(line[0]) in peeks:
			peeks[str(line[0])].append(line[1])
		else:
			peeks[str(line[0])] = [line[1]]
		if str(line[1]) in peeks:
			peeks[str(line[1])].append(line[0])
		else:
			peeks[str(line[1])] = [line[0]]
				
	return peeks
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[[int(j) for j in input().split()]for _ in range(M)]
con=[[False]*(N+1) for _ in range(N+1)]
for i in range(M):
  a,b=AB[i]
  con[a][b] =True
  con[b][a]=True
ans=0
for i in range(1,N+1):
  for  j in range(1,N+1):
    if con[i][j] and all(con[i][k]and con[k][j] for k in range(1,N+1) if k!=i and k!=j):
      ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#075-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
#UnionFindクラス
class UnionFind(object):
 
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
 
    def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
    # xとyの根を結合させる
    def union(self, 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
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
    def same(self, x, y):
        return self.find(x) == self.find(y)
n,m=IL()
nl=[]
for i in range(m):
    f,t=IL()
    nl.append([f-1,t-1])
ans=0
for i in range(m):
    t=nl[i]
    nl.remove(t)
    uf=UnionFind(n)
    for e in nl:
        uf.union(e[0],e[1])
    nl.append(t)
    for j in range(n):
        for k in range(n):
            if not uf.same(j,k):
                ans+=1
                break
            break
        break
print(ans)

Submission status: Wrong Answer

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
n,m=IL()
nl=[[0 for i in range(n)] for j in range(n)]
used=[[False for i in range(n)] for j in range(n)]
for i in range(m):
    f,t=IL()
    nl[f-1][t-1]=1
    nl[t-1][f-1]=1
cnt=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if nl[i][j]==1 and nl[i][k]+nl[k][j]==2 and not used[i][j]:
                cnt+=1
                used[i][j]=True
print(m-cnt//2)

Submission status: Wrong Answer

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
n,m=IL()
nl=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    f,t=IL()
    nl[f-1][t-1]=1
    nl[t-1][f-1]=1
cnt=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if nl[i][j]==1 and nl[i][k]+nl[k][j]==2:
                cnt+=1
print(m-cnt//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
    
def dfs(x):
    global flag
    flag[x] = True
    for k in range(n):
        if bridge[x][k] == True:
            bridge[x][k] = False
            dfs(k)
            
ans = 0
for i in range(m):
    bridge = [[False for i in range(n)] for i in range(n)]
    for j in ab[0:i] + ab[i+1:n]:
        bridge[j[0] - 1][j[1] - 1] = True
        bridge[j[1] - 1][j[0] - 1] = True   
    flag = [False for j in range(n)]
    dfs(0)
    if flag.count(False) > 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
    
def dfs(x):
    global flag
    flag[x] = True
    for k in range(n):
        if bridge[x][k] == True:
            bridge[x][k] = False
            dfs(k)
            
ans = 0
for i in range(n):
    bridge = [[False for i in range(n)] for i in range(n)]
    for j in ab[0:i] + ab[i+1:n]:
        bridge[j[0] - 1][j[1] - 1] = True
        bridge[j[1] - 1][j[0] - 1] = True   
    flag = [False for j in range(n)]
    dfs(0)
    if flag.count(False) > 0:
        ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
c=defaultdict(list)
n,m=map(int,input().split())
for s in range(m):
  a,b=map(int,input().split())
  c[a].append(b)
  c[b].append(a)
for t in range(100):
  for s in range(1,n+1):
    if len(c[s])==1:
      c[c[s][0]].remove(s)
      del c[s]
print(n-len(list(c)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
c=defaultdict(list)
n,m=map(int,input().split())
for s in range(m):
  a,b=map(int,input().split())
  c[a].append(b)
  c[b].append(a)
for s in range(1,n+1):
  if len(c[s])==1:
    c[c[s][0]].remove(s)
    del c[s]
print(n-len(list(c)))

Submission status: Wrong Answer

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

v = [i for i in range(1,N+1)]
e = [[]]*(N+1)
for i in range(M):
  a, b = map(int,input().split())
  e[a] = e[a] + [b]
  e[b] = e[b] + [a]

def dfs(v, e):
  for num in v:
    if(len(e[num]) == 1):
      tmp_num = e[num][0]
      v.remove(num)
      e[num] = []
      e[tmp_num].remove(num)
      print(e,v)
      return dfs(v, e)+1
  return 0
print(dfs(v, e))

Submission status: Wrong Answer

Solution code:
import copy

n, m = map(int, input().split())
array = [[int(x) for x in input().split()] for y in range(m)]
t = copy.copy(array)


def solver(start, array, visited, cnt):
    if visited[start]:
        return cnt
    else:
        visited[start] = True

    for i in array[start]:
        if len(set(visited)) == 1:
            return 1
        else:
            cnt = solver(i, array, visited, cnt)

    return cnt


res = 0
res2 = 0
for i in range(m):
    tmp = array[:i] + array[i + 1:]
    modify = [[] for x in range(n + 1)]
    for value1, value2 in tmp:
        modify[value1].append(value2)
        modify[value2].append(value1)

    visited = [False if x != 0 and x != 1 else True for x in range(n + 1)]
    if not modify[1]:
        continue

    for i in modify[1]:
        res += solver(i, modify, visited, 0)
    else:
        res2 += 1 if res > 0 else 0

print(m - res2)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
nums = [[] for _ in range(n)]
roads = []
cou = 0

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nums[a].append(b)
    nums[b].append(a)
    roads.append([a, b])
    
def check(a, b, path):
    global cou
    n = path[len(path) - 1]
    if b == n:
        return 1
    
    else:
        for x in nums[n]:
            if x not in path:
                path.append(x)
                check(a, b, path)
                path.pop()


for a, b in roads:
    nums[a].remove(b)
    nums[b].remove(a)
    if check(a, b, [a]) == 1:
        cou += 1
    nums[a].append(b)
    nums[b].append(a)


print(cou)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# construct indirectional graphs
edges = [[] for _ in range(n)]
for i, j in li:
    i -= 1
    j -= 1
    edges[i].append(j)
    edges[j].append(i)

import copy
edges2 = copy.deepcopy(edges)

S = deque()
S.append([0])
while len(S) > 0:
    path = S.pop()
    # if full path,
    if len(path) == n:
        # used path list
        used = [[] for _ in range(n)]
        for i, j in zip(path[:-1], path[1:]):
            used[i].append(j)
        # delete unused edges
        for i in range(len(edges2)):
            for j in edges2[i][::-1]:
                if j not in used[i]:
                    edges2[i].remove(j)
        continue
    for v in edges[path[-1]]:
        if v not in path:
            S.append(path + [v])

ans = sum(len(e) for e in edges2)

print(ans)

Submission status: Wrong Answer

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


def dfs(i):
    visited.add(i)
    for k in From[i]:
        if k not in visited:
            dfs(k)
    for k in To[i]:
        if k not in visited:
            dfs(k)

def bridge(j):
    for i in Edge:
        if i == j:
            continue
        else:
            From[i[0]-1].append(i[1]-1)
            To[i[1]-1].append(i[0]-1)
    dfs(0)
    return True if visited.__len__() != N else False
ans = 0
for j in Edge:
    From = [[] for i in range(N)]
    To = [[] for i in range(N)]
    visited = set()
    ans += bridge(j)
    print(From)
    print(To)
    print(visited)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
count = [0]*N
ans = -1
for i in range(M):
    a,b = map(int,input().split())
    count[a-1] += 1
    count[b-1] += 1
for i in range(N):
    if count[i] <= 1:
        break
    if i == N-1:
        print(0)
        exit()
for e in count:
    if e <= 2:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
count = [0]*N
ans = -1
for i in range(M):
    a,b = map(int,input().split())
    count[a-1] += 1
    count[b-1] += 1
if set(count) == {2}:
    print(0)
    exit()
for e in count:
    if e <= 2:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m = (int(i) for i in input().split())
array = np.zeros(n)
array2 = np.ones(n)+np.ones(n)
for i in range(m):
 a,b = (int(i) for i in input().split())
 array[a-1] += 1
 array[b-1] += 1
ct = -1
for j in array:
 if j <= 2:
  ct += 1
if ((array == array2).all()) == True:
  ct = 0
print(ct)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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

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

    def size(self, x):
        return len(set(self.par))

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

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

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
e = [ [] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    
visited = [False]*N
def dfs(cur):
    global visited
    # print(cur, visited)
    if all(v for v in visited): # すべて訪問可能
        return 
    for nex in e[cur]:
        if visited[nex]:
            continue
        visited[nex]=True
        dfs(nex)
    return 

ans = 0
for i in range(len(e)):
    for c in e[i]:
        if c<i: 
            continue
        e[i].remove(c)
        e[c].remove(i)
        visited = [False]*N
        dfs(1)
        if all(v for v in visited):
            ans += 1
        e[i].append(c)
        e[c].append(i)
        
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [set() for i in range(n)]
for i in range(m):
    s, t = map(int, input().split())
    a[s-1].add(t)
    a[t-1].add(s)

ans = 0
for i in range(n):
    for j in list(a[i]):
        if a[i] & a[j-1] == set():
            ans += 1
print(ans//2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
count = 0
#print(n,m,edges)

for x in edges:
    l = list(range(n))
    for y in edges:
        if y != x:
            for i in range(n):
                if l[i]==l[y[1]-1]:
                    l[i]=l[y[0]-1]
                else:
                    l[i]=l[i]
        #print(l)
    if len(set(l)) != 1:
        count += 1

print(count)

Submission status: Wrong Answer

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))
    print(l)
    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)]
            print(l)
    if len(set(l)) != 1:
        count += 1

print(count)

Submission status: Wrong Answer

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

for x in edges:
    l = list(range(n))
    print(l)
    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)]
            print(l)
    if len(set(l)) != 1:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def solve(N, M, ABs):
    ans = 0
    for i in range(M):
        m = {j: j for j in range(N)}
        for k, (a, b) in enumerate(ABs):
            a -= 1
            b -= 1
            if k == i:
                continue
            d = min(m[a], m[b])
            for mk in m:
                if m[mk] == m[a] or m[mk] == m[b]:
                    m[mk] = d
        if len(set(m.values())) != 1:
            ans += 1
    return ans

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

Submission status: Wrong Answer

Solution code:
import sys

#よくわからんのでとりあえず環をひとつみつけてその分だけ引き算
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    def addSpan(d,a,b):
        if a in d:
            d[a].add(b)
        else:
            d[a]={b}
    dT ={}
    for a,b in aAB:
        addSpan(dT,a,b)
        addSpan(dT,b,a)

    dsVisited = set()
    aPath = []
    def digRoute(n,o,p,iDepth):
        if n in dsVisited:
            iL = len(aPath)
            if iL > 2 :
                iV = aPath.index(aPath[-1])
                if iV == iL-1:
                    iD = iL
                else:
                    iD = iL - iV -1
                print(iM-iD)
                exit()
        dsVisited.add(n)
        for i in dT[n] - {p}:
            aPath.append(i)
            digRoute(i,o,n,iDepth)
            aPath.pop()
    digRoute(1,1,0,0)
    print(iM)
解()

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]

def dfs(i):
    for j in range(1,N+1):
        if visit[j]:
            continue
        if not path[i][j]:
            continue
        visit[j] = True
        X = dfs(j)
    return visit

N, M = inpl()
path = [[False for _ in range(N+1)] for i in range(N+1)]
visit = [False for _ in range(N+1)]
visit[0] = visit[1] = True
H = []
for i in range(M):
    a,b = inpl()
    path[a][b] = path[b][a] = True
    H.append((a,b))
    
ans = 0    
for st,en in H:
    path[st][en] = path[en][st] = False
    if False in dfs(1):
        ans += 1
    print(dfs(1))
    path[st][en] = path[en][st] = True
    for i in range(2,N+1):
        visit[i] = False
print(ans)

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]

N, M = inpl()
ab = [inpl() for _ in range(M)]
from copy import deepcopy
ab1 = []
ans = 0

while ab1 != ab:
    for i in range(1,N+1):
        ctr = 0
        for j,k in ab:
            if i == j or i == k:
                ctr += 1
            if ctr > 1:
                break
        if ctr ==1:
            for j,k in ab:
                if i == j or i == k:
                    ab.remove([j,k])
                    ans +=1
                    break
    ab1 = deepcopy(ab)
print(ans)

Submission status: Wrong Answer

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

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

def ret_list(a,p_dict):
    if a not in p_dict:
        return [a]
    else:
        temp = []
        for p in p_dict[a]:
            temp += [p] + ret_list(p,p_dict)
        return temp

def check_path(a,b,path_dict):
    a_list = ret_list(a,path_dict)
    b_list = ret_list(b,path_dict)

    c_set = set(a_list) & set(b_list)

    if len(c_set) > 0:
        return True
    else:
        return False

bridge_cnt = 0
for i in range(M): #M
    ab_c = list(ab)
    ab_c.pop(i)
    ab_dict = {}
    for a,b in ab_c:
        if a in ab_dict:
            ab_dict[a].append(b)
        else:
            ab_dict[a] = [b]

    for j in range(2,N+1):
        if check_path(1,j,ab_dict):
            pass
        else:
            bridge_cnt += 1
            break

print(bridge_cnt)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N, M = [int(i) for i in sys.stdin.readline().split()]
edges = [[] for _ in range(N)]
for l in sys.stdin.readlines():
  a, b = [int(i)-1 for i in l.strip().split()]
  edges[a].append(b)
  edges[b].append(a)

def flatten(l):
  return list(itertools.chain.from_iterable(l))

def is_spanning_tree(edges):
  new_edges = [[] for _ in range(N)]
  for a, b in edges:
    return 1
    new_edges[a].append(b)
    new_edges[b].append(a)
  edges = new_edges
  nodes = set([0])
  next_node_candidates = set(flatten([edges[n] for n in nodes]))
  while next_node_candidates:
    nodes.add(list(next_node_candidates)[0])
    next_node_candidates = set(flatten([edges[n] for n in nodes]))
    next_node_candidates = nodes ^ next_node_candidates #まだ追加されていないcandidate
  return True if len(nodes) == N else False

cnt = 0
edges = flatten([[(i, j) for j in edges[i] if i>=j] for i in range(N)])
incomplete_graphs = [[edges[j] for j in range(len(edges)) if i != j] for i in range(len(edges))]
spanning_trees = [1 if not is_spanning_tree(graph) else 0 for graph in incomplete_graphs]
print(len(spanning_trees))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():

    global count
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [long(input_raw[0]), long(input_raw[1])]
    adj_list = {}
    edge_list = []
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        if a not in adj_list:
            adj_list[a] = [b]
        else:
            adj_list[a].append(b)

        if b not in adj_list:
            adj_list[b] = [a]
        else:
            adj_list[b].append(a)
        edge_list.append((a, b))
    

    count = 0
    for i in range(M):
        (a, b) = edge_list[i]
        is_visit = [False for j in range(N + 1)]
        visit_count = 0
        q = deque([1])
        while 1:
            #print q
            if len(q) <= 0: break;
            
            nd = q.popleft()
            visit_count += 1
            is_visit[nd] = True
            for adj in adj_list[nd]:
                if (nd, adj) != (a, b) and (nd, adj) != (b, a) and is_visit[adj] == False:
                    q.append(adj)
                    is_visit[adj] = True
        if visit_count < N:
            count += 1


    print count

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():

    global count
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [long(input_raw[0]), long(input_raw[1])]
    adj_list = {}
    edge_list = []
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        if a not in adj_list:
            adj_list[a] = [b]
        else:
            adj_list[a].append(b)

        if b not in adj_list:
            adj_list[b] = [a]
        else:
            adj_list[b].append(a)
        edge_list.append((a, b))
    

    count = 0
    for i in range(M):
        (a, b) = edge_list[i]
        is_visit = [False for j in range(N + 1)]
        visit_count = 0
        q = deque([1])
        while 1:
            if len(q) <= 0: break;
            
            nd = q.popleft()
            visit_count += 1
            is_visit[nd] = True
            for adj in adj_list[nd]:
                if (nd, adj) != (a, b) and (nd, adj) != (b, a) and is_visit[adj] == False:
                    q.append(adj)
        if visit_count < N:
            count += 1


    print count



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():

    global count
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [long(input_raw[0]), long(input_raw[1])]
    adj_list = {}
    edge_list = []
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        if a not in adj_list:
            adj_list[a] = [b]
        else:
            adj_list[a].append(b)

        if b not in adj_list:
            adj_list[b] = [a]
        else:
            adj_list[b].append(a)
        edge_list.append((a, b))
    

    count = 0
    for i in range(M):
        (a, b) = edge_list[i]
        is_visit = [False for j in range(N + 1)]
        visit_count = 0
        q = deque([1])
        while 1:
            if len(q) <= 0: break;
            
            nd = q.popleft()
            visit_count += 1
            is_visit[nd] = True
            for adj in adj_list[nd]:
                if (nd, adj) != (a, b) and (nd, adj) != (b, a) and is_visit[adj] == False:
                    q.append(adj)
        if visit_count != N:
            count += 1


    print count



if __name__ == '__main__':
    main()