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 math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A, B = [], []
for i in range(M):
    a, b = LI()
    A.append(a)
    B.append(b)

"""
頂点ごとにみる。
その頂点につながっている辺を洗い出す
洗い出した辺の頂点同士がつながっているか確認する
最終的に自分のもとに戻ってこれるか。
dfsで全経路を洗い出す
1とそれ以外が全部つながるか。
2とそれ以外が全部つながるかを調査すればよい
"""

#  def dfs(reached_nodes, lines):
#      print('df', reached_nodes, lines, file=sys.stderr)
#      # 最初に与えられた線からたどっていって、すべての線を洗い出す。すべての頂点が入っていればおK
#      # このノードにつながっている辺をみつける
#      for line in lines:
#          if line[0] in reached_nodes or line[1] in reached_nodes:
#              # 既に到達しているnodeに入っている場合
#              new_lines = [l for l in lines if l != line]
#              if not dfs(reached_nodes + line, new_lines):
#                  # 全部つながることが確認された場合
#                  return False
#      else:
#          # 一回もひかからなかったので終了
#          print('r', reached_nodes, file=sys.stderr)
#          if len(set(reached_nodes)) < N:
#              print('True', file=sys.stderr)
#              # 無理でした。
#              return True
#          else:
#              return False
def dfs(visited_nodes, lines):
    print(visited_nodes, file=sys.stderr)
    if len(set(visited_nodes)) == N:
        print('False',file=sys.stderr)
        return False
    # 現在のノード
    for l in lines:
        if l[0] in visited_nodes or l[1] in visited_nodes:
            if not (l[0] in visited_nodes and l[1] in visited_nodes):
                return dfs(visited_nodes + l, lines)
    else:
        if len(set(visited_nodes)) == N:
            return False
        # 全部見たけどなかった。橋なのでTrue
        print('True', file=sys.stderr)
        return True


ans = 0
for idx in range(N):
    # idx番目の線をなくす
    lines = []
    for m in range(M):
        if m == idx:
            continue
        else:
            lines.append([A[m], B[m]])
    print('idx, lines', idx, lines, file=sys.stderr)
    # 各頂点が全頂点とつながっているか確認
    # ただたんに全頂点が入っているだけでは断絶の可能性があるので不十分
    #  if dfs(lines[0][:1], lines):
    if len(lines) == 0:
        print(1)
        exit()
    if dfs(lines[0], lines):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A, B = [], []
for i in range(M):
    a, b = LI()
    A.append(a)
    B.append(b)

"""
頂点ごとにみる。
その頂点につながっている辺を洗い出す
洗い出した辺の頂点同士がつながっているか確認する
最終的に自分のもとに戻ってこれるか。
dfsで全経路を洗い出す
1とそれ以外が全部つながるか。
2とそれ以外が全部つながるかを調査すればよい
"""

#  def dfs(reached_nodes, lines):
#      print('df', reached_nodes, lines, file=sys.stderr)
#      # 最初に与えられた線からたどっていって、すべての線を洗い出す。すべての頂点が入っていればおK
#      # このノードにつながっている辺をみつける
#      for line in lines:
#          if line[0] in reached_nodes or line[1] in reached_nodes:
#              # 既に到達しているnodeに入っている場合
#              new_lines = [l for l in lines if l != line]
#              if not dfs(reached_nodes + line, new_lines):
#                  # 全部つながることが確認された場合
#                  return False
#      else:
#          # 一回もひかからなかったので終了
#          print('r', reached_nodes, file=sys.stderr)
#          if len(set(reached_nodes)) < N:
#              print('True', file=sys.stderr)
#              # 無理でした。
#              return True
#          else:
#              return False
def dfs(visited_nodes, lines):
    print(visited_nodes, file=sys.stderr)
    if len(set(visited_nodes)) == N:
        print('False',file=sys.stderr)
        return False
    # 現在のノード
    for l in lines:
        if l[0] in visited_nodes or l[1] in visited_nodes:
            if not (l[0] in visited_nodes and l[1] in visited_nodes):
                return dfs(visited_nodes + l, lines)
    else:
        # 全部見たけどなかった。橋なのでTrue
        print('True', file=sys.stderr)
        return True


ans = 0
for idx in range(N):
    # idx番目の線をなくす
    lines = []
    for m in range(M):
        if m == idx:
            continue
        else:
            lines.append([A[m], B[m]])
    print('idx, lines', idx, lines, file=sys.stderr)
    # 各頂点が全頂点とつながっているか確認
    # ただたんに全頂点が入っているだけでは断絶の可能性があるので不十分
    #  if dfs(lines[0][:1], lines):
    if len(lines) == 0:
        print(1)
        exit()
    if dfs(lines[0], lines):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
A, B = [], []
for i in range(M):
    a, b = LI()
    A.append(a)
    B.append(b)

"""
頂点ごとにみる。
その頂点につながっている辺を洗い出す
洗い出した辺の頂点同士がつながっているか確認する
最終的に自分のもとに戻ってこれるか。
dfsで全経路を洗い出す
1とそれ以外が全部つながるか。
2とそれ以外が全部つながるかを調査すればよい
"""

#  def dfs(reached_nodes, lines):
#      print('df', reached_nodes, lines, file=sys.stderr)
#      # 最初に与えられた線からたどっていって、すべての線を洗い出す。すべての頂点が入っていればおK
#      # このノードにつながっている辺をみつける
#      for line in lines:
#          if line[0] in reached_nodes or line[1] in reached_nodes:
#              # 既に到達しているnodeに入っている場合
#              new_lines = [l for l in lines if l != line]
#              if not dfs(reached_nodes + line, new_lines):
#                  # 全部つながることが確認された場合
#                  return False
#      else:
#          # 一回もひかからなかったので終了
#          print('r', reached_nodes, file=sys.stderr)
#          if len(set(reached_nodes)) < N:
#              print('True', file=sys.stderr)
#              # 無理でした。
#              return True
#          else:
#              return False
def dfs(visited_nodes, lines):
    print(visited_nodes, file=sys.stderr)
    if len(set(visited_nodes)) == N:
        print('False',file=sys.stderr)
        return False
    # 現在のノード
    for l in lines:
        if l[0] in visited_nodes or l[1] in visited_nodes:
            if not (l[0] in visited_nodes and l[1] in visited_nodes):
                return dfs(visited_nodes + l, lines)
    else:
        # 全部見たけどなかった。橋なのでTrue
        print('True', file=sys.stderr)
        return True


ans = 0
for idx in range(N):
    # idx番目の線をなくす
    lines = []
    for m in range(M):
        if m == idx:
            continue
        else:
            lines.append([A[m], B[m]])
    print('idx, lines', idx, lines, file=sys.stderr)
    # 各頂点が全頂点とつながっているか確認
    # ただたんに全頂点が入っているだけでは断絶の可能性があるので不十分
    #  if dfs(lines[0][:1], lines):
    if dfs(lines[0], lines):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*M]
g=[set() for _ in [0]*N]
[g[b-1].add(a-1) for a,b in ab]
[g[a-1].add(b-1) for a,b in ab]
q=[i for i,gg in enumerate(g) if len(gg)==1]
cnt=0
while(q):
    cnt+=len(q)
    for i in q:
        g[i]=set()
        for j in range(N):
            g[j]=g[j]-{i}
    q=[i for i,gg in enumerate(g) if len(gg)==1]
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
c=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    c[a].append(b)
    c[b].append(a)
def des(c,res):
    for i in range(1,n+1):
        if len(c[i])==1:
            c[c[i][0]].remove(i)
            c[i]=[]
            res+=1
    return res
print(des(c,0))

Submission status: Wrong Answer

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]

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


    def find_root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find_root(self.par[x])
            return self.par[x]
    

    def merge(self, x, y):
        x, y = self.find_root(x), self.find_root(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


    def issame(self, x, y):
        return self.find_root(x) == self.find_root(y)


    def get_size(self, x):
        x = self.find_root(x)
        return self.size[x]

ans = 0
data = []
for i in range(M):
    a, b = [int(_) for _ in stdin.readline().rstrip().split()]
    a, b = a-1, b-1
    data.append((a, b))

for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        uf.merge(data[j][0], data[j][1])
    if uf.get_size(0) != N:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
node=[None for i in range(m)]#辺のデータをリストとして保管
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(m):
    a,b=map(int,input().split())
    graph[a-1][b-1],graph[b-1][a-1]=True,True
    node[i]=[a-1,b-1]
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
ans=0
for i in range(m):
    graph[node[i][0]][node[i][1]],graph[node[i][1]][node[i][0]]=False,False #m本の辺について、一本ずつ辺を無視していく。その際にグラフが非連結となったらその辺は橋となる（橋の定義通り調べていく）
    for j in range(n):visited[j]=False#初期化
    dfs(0)
    for h in range(n):
        if visited[h]==False:
            ans+=1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import chain
from collections import Counter

N, M = map(int, input().split())
ctr = 0
arr = [list(map(int, input().split())) for i in range(M)]
flatten_arr = list(chain.from_iterable(arr))
dic = Counter(flatten_arr)

for i in dic.values():
    if i < 3:
        ctr += 1
if ctr > 0:
    print(ctr - 1)
else:
    print(0)

Submission status: Wrong Answer

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

def test(k):
    d = {i + 1 : [] for i in range(n)}
    for i, (a, b) in enumerate(es):
        if i == k:
            continue
        d[a].append(b)
        d[b].append(a)
    q = [1]
    visited = set([])
    while True:
        if len(q) == 0:
            if len(visited) == n:
                return 0
            else:
                return 1
        q2 = q[:]
        q = []
        for v in q2:
            if v not in visited:
                visited.add(v)
                q.extend(d[v])
ans = 0
for k in range(n-1):
    ans += test(k)
print(ans)

Submission status: Wrong Answer

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

def test(k):
    d = {i + 1 : [] for i in range(n)}
    for i, (a, b) in enumerate(es):
        if i == k:
            continue
        d[a].append(b)
        d[b].append(a)
    q = [1]
    visited = set([])
    while True:
        if len(q) == 0:
            if len(visited) == n:
                return 0
            else:
                return 1
        q2 = q[:]
        q = []
        for v in q2:
            if v not in list(visited):
                visited.add(v)
                q.extend(d[v])
ans = 0
for k in range(n):
    ans += test(k)
print(ans)

Submission status: Wrong Answer

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

def test(k):
    d = {i + 1 : [] for i in range(n)}
    for i, (a, b) in enumerate(es):
        if i == k:
            continue
        d[a].append(b)
        d[b].append(a)
    q = [1]
    visited = set([])
    while True:
        if len(q) == 0:
            if len(visited) == n:
                return 0
            else:
                return 1
        q2 = q[:]
        q = []
        for v in q2:
            if v not in visited:
                visited.add(v)
                q.extend(d[v])
ans = 0
for k in range(n):
    ans += test(k)
print(ans)

Submission status: Wrong Answer

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

u = 0
s = []
non_bridge = []
while True:
    if u in s:
        tmp = s[s.index(u):]
        tmp.append(u)
        if len(tmp)>=4:
            for i in range(len(tmp)-1):
                if sorted(tmp[i:i+2]) not in non_bridge:
                    non_bridge.append(sorted(tmp[i:i+2]))
        u = s.pop()
    elif len(g[u]) > 0:
        s.append(u)
        j = -1
        for i in range(len(g[u])):
            if g[u][i] in s:
                j = i
        u = g[u].pop(j)
    else:
        u = s.pop()
    if len(s) == 0:
        break
print(m-len(non_bridge))

Submission status: Wrong Answer

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

u = 0
s = []
non_bridge = []
while True:
    if u in s:
        tmp = s[s.index(u):]
        tmp.append(u)
        if len(tmp)>=4:
            for i in range(len(tmp)-1):
                if sorted(tmp[i:i+2]) not in non_bridge:
                    non_bridge.append(sorted(tmp[i:i+2]))
        u = s.pop()
    elif len(g[u]) > 0:
        s.append(u)

        u = g[u].pop()
    else:
        u = s.pop()
    if len(s) == 0:
        break
print(m-len(non_bridge))

Submission status: Wrong Answer

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

u = 0
s = []
non_bridge = []
while True:
    if u in s:
        tmp = s[s.index(u):]
        if len(tmp)>=3:
            for i in range(len(tmp)-1):
                if sorted(tmp[i:i+2]) not in non_bridge:
                    non_bridge.append(sorted(tmp[i:i+2]))
            if sorted([tmp[0], tmp[-1]]) not in non_bridge:
                non_bridge.append(sorted([tmp[0], tmp[-1]]))
        u = s.pop()
    elif len(g[u]) > 0:
        s.append(u)

        u = g[u].pop()
    else:
        u = s.pop()
    if len(s) == 0:
        break
print(m-len(non_bridge))

Submission status: Wrong Answer

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

u = 0
s = []
non_bridge = []
while True:
    if u in s:
        tmp = s[s.index(u):]
        if len(tmp)>=3:
            for i in range(len(tmp)-1):
                if sorted(tmp[i:i+2]) not in non_bridge:
                    non_bridge.append(sorted(tmp[i:i+2]))
            non_bridge.append(sorted([tmp[0], tmp[-1]]))
        u = s.pop()
    elif len(g[u]) > 0:
        s.append(u)

        u = g[u].pop()
    else:
        u = s.pop()
    if len(s) == 0:
        break
print(m-len(non_bridge))

Submission status: Wrong Answer

Solution code:
def dfs(AB, C, v):
    if all(C) is True:
        return False
    if len(AB) == 0:
        if all(C) is True:
            return False
        return True
    f = True
    for i, (a, b) in enumerate(AB):
        ab = AB.pop(i)
        if a == v:
            C[a] = True
            C[b] = True
            f = dfs(AB[::], C[::], b)
        elif b == v:
            C[a] = True
            C[b] = True
            f = dfs(AB[::], C[::], a)
        AB.insert(i, ab)
    return f


def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(M):
        a, b = map(int, input().split())
        AB.append((a - 1, b - 1))
    C = [False] * N
    ans = 0
    for i in range(M):
        ab = AB.pop(i)
        if dfs(AB[::], C[::], 0) is True:
            ans += 1
        AB.insert(i, ab)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[list() for _ in range(n+1)]
for _ in range(m):
	a,b=map(int,input().split())
	g[a].append(b)
	g[b].append(a)
ed=set()
q=[i for i in range(n+1) if len(g[i])==1]
cnt=0
for i in q:
	if i not in ed:
		ed.add(i)
		x=g[i][0]
		cnt+=1
		while x not in ed and len(g[x])==2:
			cnt+=1
			ed.add(x)
			p=x
			x=g[x][0] if g[x][0] !=p else g[x][1]
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
graph=list([0]*N for _ in range(N))
ans=0
for a,b in ab:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

def dfs(s):
    visited[s]=1
    for i in range(N):
        if graph[s][i]==0 or visited[s]==1:
            continue
        dfs(i)

for a,b in ab:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited=[0]*N
    dfs(0)
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
    if sum(visited)<N:
        ans+=1


print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
edges=list([0]*N for _ in range(N))
ans=0
for a,b in ab:
    edges[a - 1][b - 1] = 1
    edges[b - 1][a - 1] = 1

def dfs(s):
    visited[s]=1
    for i in range(N):
        if edges[s][i]==0 or visited[s]==1:
            continue
        dfs(i)

for a,b in ab:
    edges[a - 1][b - 1] = 0
    edges[b - 1][a - 1] = 0
    visited=[0]*N
    dfs(0)
    if sum(visited)<N:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()

N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    ab.append((a,b))
ans=0
for i in range(N):
    U=[UnionFindNode(k) for k in range(N)]
    for j in range(M):
        if i==j:
            x=ab[i][0]
            y=ab[i][1]
        else:
            U[ab[j][0]].unite(U[ab[j][1]])
    if not(U[x].is_group(U[y])):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque

def read_input():
    n, m = map(int, input().split())

    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a, b))

    return n, m, edges


def check_graph(n, edges):
    nodes = list(range(1, n + 1))

    trans = {i: [] for i in nodes}
    for e in edges:
        trans[e[0]].append(e[1])
        trans[e[1]].append(e[0])

    node_q = deque()
    node_q.appendleft(nodes[0])
    searched = []
    while len(node_q) > 0:
        curr = node_q.popleft()
        searched.append(curr)
        target = trans[curr]

        for t in target:
            if t not in searched:
                node_q.appendleft(t)

        searched.sort()

    if searched == nodes:
        return True
    else:
        return False


def submit():
    n, m, edges = read_input()

    count = 0
    for t in range(m):
        test = [e for i, e in enumerate(edges) if i != t]
        if check_graph(n, test):
            count += 1

    print(m - count)

if __name__ == '__main__':
    submit()

Submission status: Wrong Answer

Solution code:

from collections import deque

def read_input():
    n, m = map(int, input().split())

    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a, b))

    return n, m, edges


def check_dfs(n, edges):
    nodes = list(range(1, n + 1))

    trans = {i: [] for i in nodes}
    for e in edges:
        trans[e[0]].append(e[1])
        trans[e[1]].append(e[0])

    node_q = deque()
    node_q.appendleft(nodes[0])
    searched = []
    while searched != nodes and len(node_q) > 0:
        curr = node_q.popleft()
        searched.append(curr)
        target = trans[curr]

        for t in target:
            if t not in searched:
                node_q.appendleft(t)

        searched.sort()

    if searched == nodes:
        return True
    else:
        return False


def submit():
    n, m, edges = read_input()

    count = 0
    for t in range(m):
        test = [e for i, e in enumerate(edges) if i != t]
        if check_dfs(n, test):
            count += 1

    print(m - count)

if __name__ == '__main__':
    submit()

Submission status: Wrong Answer

Solution code:

from collections import deque

def read_input():
    n, m = map(int, input().split())

    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a, b))

    return n, m, edges


def check_dfs(n, edges):
    nodes = list(range(1, n + 1))

    trans = {i: [] for i in nodes}
    for e in edges:
        trans[e[0]].append(e[1])
        trans[e[1]].append(e[0])

    node_q = deque()
    node_q.appendleft(nodes[0])
    searched = []
    while searched != nodes and len(node_q) > 0:
        curr = node_q.popleft()
        searched.append(curr)
        target = trans[curr]

        for t in target:
            if t not in searched:
                node_q.appendleft(t)

        searched.sort()

    if searched == nodes:
        return True
    else:
        return False


def submit():
    n, m, edges = read_input()

    count = 0
    for t in range(m):
        test = [e for i, e in enumerate(edges) if i != t]
        if check_dfs(n, test):
            count += 1

    print(m - count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
f = [False] * N
v = [0] * N
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if v[a] == 0:
        v[a] = b
    else:
        f[a] = True
        f[b] = True
        f[v[a]] = True

print(M-sum(f))

Submission status: Wrong Answer

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

ans = 0
import copy

def dfs(node, visited, gr):
    global ans
    if node in visited:
        return
    elif len(visited) == N-1:
        ans += 1
        return
    visited.append(node)
    for cand in gr[node]:
        dfs(cand, visited, gr)

def gcopy(arr):
    new = []
    for a in arr:
        new.append(copy.copy(a))
    return new


for i in range(M):
    a, b = hen[i]
    g = gcopy(graph)
    g[a-1].remove(b-1)
    g[b-1].remove(a-1)
    visited = []
    dfs(0, visited, g)

print(M-ans)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
vertex=[[int(i) for i in l.split()] for l in sys.stdin]
def find(x):
  if root[x]==x:
    return x
  return find(root[x])
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  x=find(x)
  y=find(y)
  if size[x]>=size[y]:
    root[y]=x
  else:
    root[x]=y
  if size[x]==size[y]:
    size[x]+=1
ans=0
for i in range(m):
  root=[i for i in range(n+1)]
  size=[0]*(n+1)
  for j in range(m):
    if j!=i:
      if check(vertex[j][0],vertex[j][1]):
        pass
      else:
        union(vertex[j][0],vertex[j][1])
  for j in range(n-1):
    if check(j,j+1)==0:
      pass
    else:
      ans+=1
      break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=[int(val) for val in input().split()]
matrix=[[int(val) for val in input().split()]for val in range(m)]
print(n,m,matrix)
matrix=[[val[0]-1, val[1]-1] for val in matrix]
print(matrix)


adjacent=[[] for val in range(n)]
print(adjacent)
for val1 in range(m):
  for val in range(n):
    if val==matrix[val1][0]:
      adjacent[matrix[val1][0]]+=[matrix[val1][1]]
print(adjacent)  

flag=0
def dfs(goal,path):
  p=path[-1]
  if p==goal:
    flag=1
#    print(path)
     
  else:
    for x in adjacent[p]:
      if x in path:
        continue
      else:
        path.append(x)
        dfs(goal,path)
        path.pop()

print(flag)

Submission status: Wrong Answer

Solution code:
#import copy
n,m = (int(aa) for aa in input().split())
#print(n,m)

ee=[['',''] for aa in range(m)]

for aa in range(m):
    ee[aa][0],ee[aa][1] = [int(aa) for aa in input().split()]
#print(ee)

ee=[[ee[aa][0]-1,ee[aa][1]-1] for aa in range(m)]
#print(ee)

ans=0
for cc in range(m):
  xx=[int(aa) for aa in range(n)]
#  print(xx)
  for bb in range(len(ee)):
    if ee.index(ee[bb]) == cc:
      continue
    else:
      for aa in range(n):
        if xx[aa]==xx[ee[bb][1]]:
          xx[aa]=xx[ee[bb][0]]
#  print(xx)
  if len(set(xx)) > 1:
    ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n,m = (int(aa) for aa in input().split())
#print(n,m)

ee=[['',''] for aa in range(m)]
#print(e)

for aa in range(m):
  ee[aa] = [int(aa) for aa in input().split()]
#print(e)

for aa in range(m):
  for bb in range(2):
    ee[aa][bb]-=1
    
ans=0
for cc in range(len(ee)):
    tmp=copy.deepcopy(ee)
    tmp.pop(cc)
    xx=[int(aa) for aa in range(n)]
    for  bb in range(len(tmp)):
        for aa in range(n):
            if xx[aa]==xx[tmp[bb][1]]:
                xx[aa]=xx[tmp[bb][0]]
    if len(set(xx)) > 1:
        ans+=1
        
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import copy
import collections
N,M=map(int,input().split(' '))
R=[list(map(int,input().split(' '))) for i in range(M)]
Mat=[[0]*N]
for i in range(N-1):
	Mat.append([0]*N)
for r in R:
	Mat[r[0]-1][r[1]-1]=1
stack=[1]
island=[]

ans=0
Matmini=[]

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

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

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import copy
import collections

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

ans=0
Matmini=[]

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

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