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: Runtime Error

Solution code:
import queue
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y = [0] * N, [0] * N
g = [[] for _ in range(N)]

for i in range(M):
    X[i], Y[i] = map(int, input().split())

    X[i] -= 1
    Y[i] -= 1
    g[X[i]].append(Y[i])
    g[Y[i]].append(X[i])


def bfs(x, y):
    visited = [False] * N
    q = queue.Queue()
    for nx in g[x]:
        if nx == y:
            continue
        q.put(nx)

    visited[x] = True

    while not q.empty():
        cur = q.get()
        if cur == y:
            return True

        visited[cur] = True
        for nx in g[cur]:
            if visited[nx]:
                continue
            q.put(nx)

    return False

cnt = 0
for i in range(M):
    if not bfs(X[i], Y[i]):
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
# import sys
# import math
# import itertools
# from collections import deque
# from collections import defaultdict
# import heapq
# import copy
# import bisect
# import numpy as np
# from scipy.special import comb

# def my_input(): return sys.stdin.readline().rstrip()

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 main():
    N, M = map(int, input().split())

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

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if i == j:
                continue
            uf.union(a[j]-1, b[j]-1)
        if not uf.same(a[i]-1, b[i]-1):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
graph = {i+1:[] for i in range(1,n+1)}

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

ans = 0
while 1:
  count = 0
  for i in range(1,n+1):
    if len(graph[i]) == 1:
      count += 1
      a = graph[i]
      graph[a].remove(i)
      graph[i] = []
  ans += count
  if count == 0:
    break
  else:
    count = 0
print(ans)

Submission status: Runtime Error

Solution code:
# C - Bridge
# https://atcoder.jp/contests/abc075/tasks/abc075_c

from collections import deque

def dfs(start, graph):
  visited = [False] * n
  stack = deque()
  stack.append(start)
  visited[start] = True
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited

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

ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)

  if not all(dfs(i, graph)):
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
# C - Bridge
# https://atcoder.jp/contests/abc075/tasks/abc075_c

from collections import deque

def dfs(pos):
  visited = [False] * n
  stack = deque()
  stack.append(pos)
  visited[pos] = True
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited

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

ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)

  if not all(dfs(i)):
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
# C - Bridge
# https://atcoder.jp/contests/abc075/tasks/abc075_c

from collections import deque

def dfs(i):
  visited = [False] * n
  stack = deque()
  stack.append(i)
  visited[i] = True
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited

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

ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)

  if not all(dfs(i)):
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
# C - Bridge
# https://atcoder.jp/contests/abc075/tasks/abc075_c

from collections import deque

def dfs(i):
  visited = [False] * n
  stack = deque()
  stack.append(i)
  while stack:
    q = stack.popleft()
    nxts = graph[q]
    for nxt in nxts:
      if not visited[nxt]:
        visited[nxt] = True
        stack.append(nxt)
  return visited

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

ans = 0
for i in range(m):
  graph = [[] for _ in range(n)]
  for itr, (a, b) in enumerate(edge):
    if itr != i:
      graph[a - 1].append(b - 1)
      graph[b - 1].append(a - 1)

  if not all(dfs(i)):
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
def resolve():
    n,m = map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(m)]
    cnt=0
    for i in range(n):
        edge = [[] for i in range(n)]
        for j in range(n):
            if j==i:
                continue
            else:
                edge[ab[j][0]-1].append(ab[j][1]-1)
                edge[ab[j][1]-1].append(ab[j][0]-1)
        visit=[False]*n
        if i==0:
            chk=[1]
            visit[1]=True
        else:
            chk=[0]
            visit[0]=True
        while chk:
            x=chk.pop()
            visit[x]=True
            for i in edge[x]:
                if visit[i]==True:
                    continue
                chk.append(i)
        for i in visit:
            if i==False:
                cnt+=1
                break
    print(cnt)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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 same(self, x, y):
        return self.find(x) == self.find(y)

    def nums(self,x):
        return abs(self.parents[self.find(x)])

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

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

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

N, M = map(int, input().split())
A = [0]*N
B = [0]*N
for i in range(M):
    A[i],B[i] = map(int, input().split())
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j!=i:
            uf.union(A[j]-1,B[j]-1)
    if len(uf.roots())>1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse import coo_matrix, csgraph
N, M = map(int, input().split())
points = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(M))
matrix = coo_matrix(([1] * M, zip(*points)), shape=(N, N)).toarray()
total = 0
for point in points:
    matrix[point] = 0
    total += csgraph.connected_components(matrix, directed=False, return_labels=False) != 1
    matrix[point] = 1
print(total)

Submission status: Runtime Error

Solution code:
#Nはノード数、Mはエッジ数
n,m = map(int, input().split())

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

cnt=0

for x in ab:
  ls=list(range(n))
  for y in ab:
    if y !=x:
      for i in range(n)
        ls=[ls[y[0]-1] if ls[i]==ls[y[1]-1] else ls[i] for i in range(n)] #bの値を根っこ（低い方a）にする
  if len(set(ls)) !=1:
    cnt+=1

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    n, m, *ab = map(int, open(0).read().split())
    e = [set() for _ in range(n)]
    for u, v in zip(*[iter(ab)] * 2):
        e[u - 1].add(v - 1)
        e[v - 1].add(u - 1)

    ans = 0
    for _ in range(m):
        count = 0
        for i, x in enumerate(e):
            if len(x) == 1:
                e[i] = []
                e[x[0]] -= {i}
                count += 1
        if count:
            ans += count
        else:
            print(ans)
            exit()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def dfs(v1):
    if all(visited): return 1
    visited[v1] = 1
    for v2 in range(n):
        if graph[v1][v2] == 0: continue
        if visited[v2] == 1: continue
        dfs(v2)
    return 0
# nは頂点の数
n, m = MI()
ab = np.array([list(map(int,input().split()))])
a,b = ab.T[0]-1,ab.T[1]-1

#隣接行列
graph = [[0] * n for _ in range(n)]

ans = 0
for a, b in zip(a,b):
    for aa,bb in zip(a,b): graph[aa][bb],graph[bb][aa] = 1,1
    graph[a][b],graph[b][a] = 0,0
    visited = [0]*n
    if not dfs(0): ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = list([] for _ in range(m+1))
li = list(list(map(int,input().split())) for _ in range(m))
bridge = 0
for a,b in li:
  l[a].append(b)
  l[b].append(a)
for a,b in li:
  if len(l[a])==1 or len(l[b])==1:
    bridge += 1
  elif len(l[a])==2 :
    c,d = l[a]
    if len(l[c])==1 or len(l[d])==1:
      bridge += 1
  elif len(l[b])==2 :
    c,d = l[b]
    if len(l[c])==1 or len(l[d])==1:
      bridge += 1
print(bridge)

Submission status: Runtime Error

Solution code:
from sys import stdin


def dfs(g, v, visited):
    visited[v] = True

    for v2 in range(len(visited)):
        if not g[v][v2]:
            continue
        if visited[v2]:
            continue
        dfs(g, v2, visited)


def main():
    n, m = map(int, stdin.readline().split())
    ab = [list(map(int, stdin.readline().split())) for _ in range(m)]
    g = [[False] * n for _ in range(n)]
    for a, b in ab:
        g[a - 1][b - 1] = True
        g[b - 1][a - 1] = True

    ans = 0

    for i in range(m):
        visited = [False for _ in range(n)]
        a, b = ab[i]
        g[a - 1][b - 1] = False
        g[b - 1][a - 1] = False

        dfs(g, i, visited)

        check = False
        for v in visited:
            if not v:
                check = True
        if check:
            ans += 1

        g[a - 1][b - 1] = True
        g[b - 1][a - 1] = True

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin


def dfs(g, v, visited):
    visited[v] = True

    for v2 in range(len(visited)):
        if (not g[v][v2]) or visited[v2]:
            continue
        dfs(g, v2, visited)


def main():
    n, m = map(int, stdin.readline().split())
    ab = [list(map(int, stdin.readline().split())) for _ in range(m)]
    g = [[False] * n for _ in range(n)]
    for a, b in ab:
        g[a - 1][b - 1] = True
        g[b - 1][a - 1] = True

    ans = 0

    for i in range(m):
        visited = [False for _ in range(n)]
        a, b = ab[i]
        g[a - 1][b - 1] = False
        g[b - 1][a - 1] = False

        dfs(g, i, visited)

        check = False
        for v in visited:
            if not v:
                check = True
        if check:
            ans += 1

        g[a - 1][b - 1] = True
        g[b - 1][a - 1] = True

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
graph=[[0 for _ in range(m)] for _ in range(m)]
for i in range(m):
  graph[ab[i][0]-1][ab[i][1]-1]=1
  graph[ab[i][1]-1][ab[i][0]-1]=1
visited=[0 for _ in range(m)]

def dfs(v):
  visited[v]=1
  for v2 in range(n):
    if graph[v][v2]==0:
      continue
    if visited[v2]==1:
      continue
    dfs(v2)

ans=0

for i in range(m):
  graph[ab[i][0]-1][ab[i][1]-1]=0
  graph[ab[i][1]-1][ab[i][0]-1]=0
  for j in range(n):
    visited[j]=0
  dfs(0)
  bridge=0
  for j in range(n):
    if visited[j]==0:
      bridge=1
  if bridge==1:
    ans+=1
  graph[ab[i][0]-1][ab[i][1]-1]=1
  graph[ab[i][1]-1][ab[i][0]-1]=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist


N, M = MAP()
L = [LIST() for i in range(M)]
graph = defaultdict(list)

for a, b in L:
    graph[a-1].append((b-1, 1))
    graph[b-1].append((a-1, 1))

ans = 0

for i in range(M):
    a, b = L[i]
    E = deepcopy(graph)
    E[a-1].remove((b-1, 1))
    E[b-1].remove((a-1, 1))
    dist = dijkstra(E, i)
    if dist.count(INF) > 0:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist


N, M = MAP()
L = [LIST() for i in range(M)]
graph = defaultdict(list)

for a, b in L:
    graph[a-1].append((b-1, 1))
    graph[b-1].append((a-1, 1))

ans = 0

for i in range(M):
    a, b = L[i]
    E = deepcopy(graph)
    E[a-1].remove((b-1, 1))
    E[b-1].remove((a-1, 1))
    if dijkstra(E, i).count(INF) >= 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
  
    def __init__(self,n):
        #par[x]==xならxというノードが根。xに親がいない
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1) 
    
    def find(self,x): #xの根を検索
        #xが根ならxを返す
        if self.par[x] == x:
            return x
        else:
			self.par[x] = self.find(self.par[x]) #パス圧縮
            return self.par[x]

    def unite(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 #rankが同じ木を繋げたとき根のランクを一つ上げる
    
    def same_check(self,x,y): #xとyが同じ集合に属しているか
        return self.find(x) == self.find(y)

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

A=[list(map(int,input().split())) for i in range(m)]
ans = 0
for i in range(m):
    uf = UnionFind(n) #
    for j in range(m):
        if i != j: #
            uf.unite(A[j][0],A[j][1])
    f = 1
    g = uf.find(1) #
    for j in range(1,n+1):
        if g != uf.find(j): #1~n(iを除く)がすべて同じ集合に属しているか
            f = 0
            break
    if not f:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [1 for _ in range(n)]
  def parent(self, x):
    if x == self.parents[x]:
      return x
    else:
      p = self.parent(self.parents[x])
      self.parents[x] = p
      return p
  def union(self, x, y):
    host = x if self.ranks[x] < self.ranks[y] else y
    guest = x+y-host
    self.ranks[host] += self.ranks[guest]
    self.parents[self.parent(guest)] = host
  def find(self, x, y):
    return self.parent(x)==self.parent(y)
  def numtrees(self):
    return len(set(self.parents))

N, M = map(int, input().split())
E = []
for _ in range(M):
  a, b = map(int, input().split())
  E.append((a-1, b-1))
ans = 0
r = 0
while r < M:
  uf = UnionFind(N)
  i = 0
  while i < M:
    if i != r:
      a, b = E[i]
      uf.union(a, b)
    i += 1
  i = 0
  while i < M:
    _ = uf.parent(i)
    i += 1
  if uf.numtrees() > 1:
    ans += 1
  r += 1
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [1 for _ in range(n)]
  def parent(self, x):
    if x == self.parents[x]:
      return x
    else:
      p = self.parent(self.parents[x])
      self.parents[x] = p
      return p
  def union(self, x, y):
    host = x if self.ranks[x] < self.ranks[y] else y
    guest = x+y-host
    self.ranks[host] += self.ranks[guest]
    self.parents[self.parent(guest)] = host
  def find(self, x, y):
    return self.parent(x)==self.parent(y)
  def numtrees(self):
    return len(set(self.parents))

N, M = map(int, input().split())
E = []
for _ in range(M):
  a, b = map(int, input().split())
  E.append((a-1, b-1))
ans = 0
r = 0
while r < M:
  uf = UnionFind(N)
  i = 0
  while i < M:
    if i != r:
      a, b = E[i]
      uf.union(a, b)
    i += 1
  i = 0
  while i < N:
    _ = uf.parent(i)
    i += 1
  if uf.numtrees() > 1:
    ans += 1
  r += 1
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [1 for _ in range(n)]
  def parent(self, x):
    if x == self.parents[x]:
      return x
    else:
      p = self.parent(self.parents[x])
      self.parents[x] = p
      return p
  def union(self, x, y):
    host = x if self.ranks[x] < self.ranks[y] else y
    guest = x+y-host
    self.ranks[host] += self.ranks[guest]
    self.parents[self.parent(guest)] = host
  def find(self, x, y):
    return self.parent(x)==self.parent(y)
  def numtrees(self):
    return len(set(self.parents))

N, M = map(int, input().split())
E = []
for _ in range(M):
  a, b = map(int, input().split())
  E.append((a-1, b-1))
ans = 0
r = 0
while r < N:
  uf = UnionFind(N)
  i = 0
  while i < M:
    if i != r:
      a, b = E[i]
      uf.union(a, b)
    i += 1
  i = 0
  while i < N:
    _ = uf.parent(i)
    i += 1
  if uf.numtrees() > 1:
    ans += 1
  r += 1
print(ans)

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

limit=50
graph=[[False]*limit for _ in range(limit)]
visited=[False]*limit

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

def main():
  n,m=LI()
  a=[[] for _ in range(n)]
  b=[[] for _ in range(n)]
  for i in range(m):
    _a,_b=LI()
    _a-=1
    _b-=1
    a[i]=_a
    b[i]=_b
    graph[_a][_b]=True
    graph[_b][_a]=True

  ans=0
  for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False

    for j in range(n):
      visited[j]=False
    dfs(n,0)
    no_visited=False
    for j in range(n):
      if visited[j]==False:
        no_visited=True
    if no_visited:
      ans+=1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True

  return ans

# main()
print(main())

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = map(int,input().split())
path = [[] for _ in range(n)]
ab = [[] for _ in range(m)]
for i in ragne(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab[i] = (a,b)
  path[a].append(b)
  path[b].append(a)
def dfs(a,b):
  que = deque()
  reach = [False]*n
  reach[0] = True
  que.append(0)
  while que:
    p = que.pop()
    for i in path[p]:
      if (p,i)!=(a,b)!=(i,p) and not reach[i]:
        p.append(i)
        reach[i] = True
  return reach != [True] * n
ans = 0
for a,b in ab:
  ans += dfs(a,b)
print(ans)

Submission status: Runtime Error

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


def resolve():
    from scipy.sparse.csgraph import connected_components  # https://note.nkmk.me/python-scipy-connected-components/
    from scipy.sparse import csr_matrix

    N, M = map(int, input().split())  # 頂点数、辺数
    A, B, C = [0] *  M, [0] * M, [1] * (M-1)
    for i in range(M):
        A[i], B[i] = map(int, input().split())
        A[i]-=1
        B[i]-=1

    cnt = 0
    for i in range(M):
        #print(B[:i] + B[i + 1:i + M] + B[i + M + 1:])
        #print(A[:i] + A[i + 1:i + M] + A[i + M + 1:])
        csr = csr_matrix((C, (A[:i] + A[i + 1:], B[:i] + B[i + 1:])), shape=(N, N))
        #print(csr)
        #print('haha')
        n, labels = connected_components(csr)
        if n == 2:
           cnt += 1
    print(cnt)


resolve()

Submission status: Runtime Error

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

def dfs(v,seen):
    if seen[v]: return
    seen[v] = True
    for nv in G[v]:
        dfs(nv,seen)

cnt = 0

for i in range(m):
    ra,rb = data[i]
    G[ra].remove(rb)
    G[rb].remove(ra)
    seen = [False]*n
    cnt += (sum(seen) == n)
    G[a].append(b)
    G[b].append(a)

print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[ [0 for _ in range(8)] for _ in range(8)]
a=[0]*m
b=[0]*m
for i in range(m):
    a[i],b[i]=map(lambda x:int(x)-1,input().split())
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
ans=0
#print(g)
for i in range(m):
#    print(i,end=' start i \n')
    g[a[i]][b[i]]=0
    g[b[i]][a[i]]=0
    vis=[0]*n
    def dfs(u):
        vis[u]=1
#        print(u,end=' dfs\n')
        for j in range(n):
            if j!=u and g[u][j]==1 and vis[j]==0:
                dfs(j)
    bridge=False
    dfs(0)
    for j in range(n):
        #print(i,vis)
        if vis[j]==0:
            bridge=True
    if bridge:
        ans+=1
    #print(i,end=' curr i \n')
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
print(ans)

Submission status: Runtime Error

Solution code:
// 深さ優先探索　計算量：O(N+M)

#include <bits/stdc++.h>
typedef long long ll;
#define MOD 1000000007

using namespace std;

const int limit = 50;

int n,m;
int a[limit],b[limit];

bool graph[limit][limit];
bool visited[limit];

void dfs(int v) {
    visited[v] = true;
    for (int v2 = 0; v2 < n; ++v2) {
        if (graph[v][v2] == false) continue; // vからv2へ路があるなら次の処理へ
        if (visited[v2] == true) continue; // v2を訪れたことがないならv2へ進みdfs
        dfs(v2);
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
    }
    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = false; // 1つ目の辺を取り除く
        for (int j = 0; j < n; j++)
        {
            visited[j] = false; // visitedを初期化
        }
        dfs(0);
        bool bridge = false;
        for (int j = 0; j < n; j++)
        {
            if(visited[j] == false) bridge = true; // 訪れていない点が1つでも存在する => ”橋”が存在する
        }
        if(bridge) ans++;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true; //取り除いた辺を元に戻す
        
        
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

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.appned(ai)
        b.appned(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: Runtime Error

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.appned(ai)
        b.appned(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: Runtime Error

Solution code:
n,m= map(int,input().split())
henl = []
usehen = [False] * n
brdic = {}
for _ in range(m):
    a,b= map(int,input().split())
    brdic[a] = brdic.get(a,[]) + [b]
    brdic[b] = brdic.get(b,[]) + [a]
    henl.append((a,b))

ordin = [-1]*(n+1)
lowlink = [-1]*(n+1)
k=[1]
bn=[0]
def dfs(node):
    ordin[node]=k[0]
    k[0]+=1
    lowlink[node]=ordin[node]
    for br in brdic[node]:
        temp = (min(node,br),max(node,br))
        if ordin[br]==-1:
            usehen[henl.index(temp)]=True
            dfs(br)
            lowlink[node] = min(lowlink[br],lowlink[node])
        else:
            if usehen[henl.index(temp)]==False:lowlink[node] = min(ordin[br],lowlink[node])
        if ordin[node] < lowlink[br]:bn[0]+=1
dfs(1)
print(bn[0])