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
n, m = map(int, input().split())
route = [[] for _ in range(n)]
vals = []
for _ in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
    route[b-1].append(a-1)
    vals.append([a-1, b-1])
ans = m
for i in range(m):
    route2 = set()
    q = queue.Queue()
    q.put(i)
    route[vals[i][0]].remove(vals[i][1])
    route[vals[i][1]].remove(vals[i][0])
    while not q.empty():
        a = q.get()
        if not a in route2:
            route2.add(a)
            for j in route[a]:
                q.put(j)
    if len(route2) == n:
        ans -= 1
    route[vals[i][0]].append(vals[i][1])
    route[vals[i][1]].append(vals[i][0])
    
print(ans)

Submission status: Runtime Error

Solution code:
from typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(b(n, m, g))


def b(n: int, m: int, g: List[Tuple[int, int]]):
    ret = 0
    for i in range(m):
        v = set()
        w = [1]
        while w:
            now = w.pop()
            v.add(now)
            for j, node in enumerate(g):
                if j == i:
                    continue
                if node[0] == now and node[1] not in v:
                    w.append(node[1])
                elif node[1] == now and node[0] not in v:
                    w.append(node[0])
        if len(v) != n:
            ret += 1
    return ret


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(b(n, m, g))


def b(n: int, m: int, g: List[Tuple[int, int]]):
    ret = 0
    for i in range(m):
        v = set()
        w = []
        w.append(1)
        while w:
            now = w.pop()
            v.add(now)
            for j, node in enumerate(g):
                if j == i:
                    continue
                if node[0] == now and node[1] not in v:
                    w.append(node[1])
                elif node[1] == now and node[0] not in v:
                    w.append(node[0])
        if len(v) != n:
            ret += 1
    return ret


if __name__ == '__main__':
    main()

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 size(self, x):
        return -self.parents[self.find(x)]

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

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

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

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

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

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


N,M = list(map(int,input().split()))

AB = []
for i in range(M):
    AB.append(list(map(int,input().split())))

out = 0
for break in range(M):
    Network = UnionFind(N)
    for j in range(M):
        if j!=break:
            A,B=AB[j][0],AB[j][1]
            Network.union(A-1, B-1)
    if Network.group_count()==2:
        out+=1
print(out)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

n,m=map(int,input().split())
pair=[i for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1
    
def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

icnt=0
for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(m):
        if ii==i:
            continue
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
#    print(i,l)
    lenpair=len(set(l))    
    if lenpair!=1:
        icnt+=1

print(icnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)

n,m=map(int,input().split())
pair=[i for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1
    
def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

icnt=0
for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(m):
        if ii==i:
            continue
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
#    print(i,l)
    lenpair=len(set(l))    
    if lenpair!=1:
        icnt+=1

print(icnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
pair=[i for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1
    
def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

icnt=0
for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(m):
        if ii==i:
            continue
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
#    print(i,l)
    lenpair=len(set(l))    
    if lenpair!=1:
        icnt+=1

print(icnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

n,m=map(int,input().split())
pair=[i for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1
    
def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

icnt=0
for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(m):
        if ii==i:
            continue
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
#    print(i,l)
    lenpair=len(set(l))    
    if lenpair!=1:
        icnt+=1

print(icnt)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heappushpop, heapreplace, heapify

n, e = map(int, input().split())
#edge_listに各辺の情報を格納する
edge_list = [[] for i in range(n)]
for _ in range(e):
    s, t, u = map(int, input().split())
    edge_list[s].append([u, t])
    edge_list[t].append([u, s])

#隣接行列及びスタートを与えると、各頂点までの最短経路を算出するダイクストラ関数
def dijkstra(edges, start):
    #startの点から各頂点までの最短距離
    d = [float("inf")] * n
    used = [False] * n
    d[start] = 0
    used[start] = True
    #各ノードへのstartからのcostを記録するlistを導入
    node_cost_list = []

    for e in edges[start]:
        heappush(node_cost_list, e)
    while len(node_cost_list):
        min_cost_node = heappop(node_cost_list)
        if used[min_cost_node[1]]:
            continue
        v = min_cost_node[1]
        d[v] = min_cost_node[0]
        used[v] = True
        for z in edges[v]:
            if not used[z[1]]:
                heappush(node_cost_list, [z[0]+d[v], z[1]])
    return d


if __name__ == "__main__":
    for k in range(n):
        print(dijkstra(edge_list, k))

Submission status: Runtime Error

Solution code:

n,m = map(int,input().split())
dic={}
ans=[]
for _ in range(m):
    a,b,=input().split()
    dic.setdefault(a,[]).append(b)
    ans.append((a,b))

for k,v in dic.items():
    for i in v:
        for j in dic.get(i,[]):
            if j in v:
                ans.remove((k,i))
                ans.remove((k,j))
                ans.remove((i,j))
print(len(ans))

Submission status: Runtime Error

Solution code:
import times, strutils, sequtils, math, algorithm, tables, sets, lists, intsets
import critbits, future, strformat, deques
template `max=`(x,y) = x = max(x,y)
template `min=`(x,y) = x = min(x,y)
let read* = iterator: string {.closure.} =
    while true: (for s in stdin.readLine.split: yield s)
proc scan(): int = read().parseInt
proc toInt(c:char): int =
    return int(c) - int('0')


var par:seq[int]  

proc root(par:var seq[int], x:int):int=
  if par[x] == x:
    return x
  else:
    par[x] = root(par, par[x])
    result = par[x]

proc unite(par:var seq[int], x,y :int)=
  var
    rx = root(par,x)
    ry = root(par,y)
  if rx == ry:
    return
  else:
    par[rx] = ry

proc same(par:var seq[int], x,y:int):bool=
  return root(par,x) == root(par,y)


proc solve():int=
  var
    (n,m) = (scan(),scan())
    usebridges = newseqwith(n,newseq[int](0))
    bridges = newseq[(int,int)](0)
  for i in 0..<m:
    bridges.add( (scan()-1,scan()-1))

  for i in 0..<m:
    par = newseq[int](n)
    for j in 0..<n:
      par[j] = j
    for j,b in bridges:
      if i!=j:
        par.unite(b[0],b[1])
    block check:
      for left in 0..<n:
        for right in 0..<n:
          if not par.same(left,right):
            result+=1
            break check
          


  
  
    

    
  
echo solve()

Submission status: Runtime Error

Solution code:
N, M = list(map(int,input().split()))
graph = [[-1 for i in range(N)] for i in range(N)]
in_list = []
for i in range(M):
    in_list.append([a, b])
    a, b = list(map(int,input().split()))
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
    
# 頂点 node を含む連結成分が木なら 1 を返す
def dfs(node, parent):
    ret = 1
    global seen
    if seen[node]:  return 0
    seen[node] = True
    for i in range(N):
        if graph[node][i] == 1 and i != parent:
            ret = min(dfs(i, node), ret)
    return ret

ans = 0

for i in range(M):
    
    graph[in_list[i][0] - 1][in_list[i][1] - 1] = -1
    graph[in_list[i][1] - 1][in_list[i][0] - 1] = -1
    
    seen = [False for _ in range(N)]
    link = 0 # 連結成分
    wood = 0 # 木の個数
    
    for j in range(N):
        if seen[j] == False:
            link += 1
            wood += dfs(j, 0)
            seen[j] = True
            
    ans += (link != 1)
    
    graph[in_list[i][0] - 1][in_list[i][1] - 1] = 1
    graph[in_list[i][1] - 1][in_list[i][0] - 1] = 1
    
print(ans)

Submission status: Runtime Error

Solution code:
#####################################################################################################
##### Low Link (橋、関節点)
#####################################################################################################

"""

計算量
O(V+E)

参考
https://algo-logic.info/bridge-lowlink/


"""



import sys
input = sys.stdin.readline
import marshal


class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.dictated == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bridge_detector(self, articular_list=False):
        """
        :param p: スタート地点
        :param save: True = 前回の探索結果を保持する
        :param articular_list: True = 関節点のリストを返す
        :return: 各点までの距離と何番目に発見したかを返す
        """


        start, time = 0, 0
        p, t = start, time
        self.parent[p] = -2
        ord = [-1]*self.n       # ord = DFS で頂点 q を何番目に探索したか
        ord[p] = t
        low = [-1]*self.n       # low = q からの 0 回以上木辺を使って前進し、後退辺を1回以下使って後退する事で到達できる頂点 p について、ord[p] の最小値
        low[p] = 0
        articular = []          # 関節点の集合
        bridge = []             # 橋の集合

        if len(edge2[p]) >= 2:
            """ 根に子が二つ異常存在する場合は、根も関節点 """
            articular.append(p)

        while True:
            if self.edges[p]:
                q = self.edges[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    if ord[q] < low[p]:
                        low[p] = ord[q]
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                """"""""""""""""""""
                ord[q] = low[q] = t + 1
                self.parent[q] = p
                p, t = q, t + 1
            else:
                if p == start and t == time:
                    break
                """ p から進める点がもう無い時の点 p における処理 """
                parent_p = self.parent[p]
                if low[p] < low[parent_p]:
                    low[parent_p] = low[p]
                """ この時点でlow[p]が確定するので、ord[parent[p]] ≤ low[p] を判定しておく"""
                if ord[parent_p] <= low[p]:
                    if ord[parent_p]:
                        articular.append(parent_p + self.decrement)
                    if ord[parent_p] < low[p]:
                        bridge.append((parent_p + self.decrement, p + self.decrement))
                """"""""""""""""""""
                p, t = self.parent[p], t - 1
                """ 点 p から親ノードに戻ってきた時の親ノードにおける処理 """
                """"""""""""""""""""
        if articular_list == False:
            return bridge
        else:
            return articular

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.dictated:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        nx.draw_networkx(G)
        plt.show()


def inc(A):
    return list(map(lambda x: x+1, A))


def dec(A):
    return list(map(lambda x: x-1, A))

###############################################################################################

N, M = map(int, input().split())
graph = Graph(N, dictated=False, decrement=True, destroy=True)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)



print(len(graph.bridge_detector(articular_list=False)))

# graph.draw()

"""
9 10
7 8
8 9
3 6
9 2
1 2
2 3
3 4
4 5
5 6
6 7

"""

Submission status: Runtime Error

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


def dfs(now):
    if not 0 in vis: 
        cnt += 1
        return None
    for new in path[now]:
        if vis[new] == 0:
            vis[new] = 1
            dfs(new)
cnt = 0
for i in range(M):
    vis  = [0 for _ in range(N)]
    a = save[i][0]
    b = save[i][1]
    path[a].remove(b)
    path[b].remove(a)
    vis[0] = 1
    dfs(0)
    path[a].append(b)
    path[b].append(a)
print(M-cnt)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
fr = [[] for _ in range(N)]

AB = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    a,b = AB[i]
    a,b = a-1,b-1
    fr[a].append(b)
    fr[b].append(a)
def dfs(fr,cur,parent,index,li):
    children = fr[cur]
    if len(children) == 0:
        return
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
cnt = 0
for i in range(M):
    a,b = AB[i]
    a,b = a-1,b-1
    used = [-1]*N #-1なら未探索。数字はrenketuのindex
    renketu = []
    index = 0
    fr[a].remove(b)
    fr[b].remove(a)
    for j in range(N):
        if used[j] != -1:
            continue
        li = [j]
        used[i] = index
        dfs(fr,j,-1,index,li)
        index += 1
        renketu.append(li)
    if len(renketu) != 1:
        cnt += 1
    fr[a].append(b)
    fr[b].append(a)
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
fr = [[] for _ in range(N)]

AB = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    a,b = AB[i]
    a,b = a-1,b-1
    fr[a].append(b)
    fr[b].append(a)
def dfs(fr,cur,parent,index,li):
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
cnt = 0
for i in range(M):
    a,b = AB[i]
    a,b = a-1,b-1
    used = [-1]*N #-1なら未探索。数字はrenketuのindex
    renketu = []
    index = 0
    fr[a].remove(b)
    fr[b].remove(a)
    for j in range(N):
        if used[j] != -1:
            continue
        li = [i]
        used[i] = index
        dfs(fr,i,-1,index,li)
        index += 1
        renketu.append(li)
    if len(renketu) != 1:
        cnt += 1
    fr[a].append(b)
    fr[b].append(a)
print(cnt)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.nodes=n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j):
        return self.find(i)==self.find(j)
    def get_parents(self):
        for n in range(self.nodes):
            selff.find(n)
        return self.parents

adj=[]
n, m = map(int,input().split())
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i==j:
            continue
        uf.unite(adj[j])
    if len(set(uf.get_parents()))!=1:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja

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

    def sequence(self,x,res):
        if self.parents[x] < 0:
            res.append(x)
            return res
        res.append(x)
        self.sequence(self.parents[x],res)
        return res

    def union(self,x,y,res):
        X = self.sequence(x,[])
        Y = self.sequence(y,[])
        if X[-1] == Y[-1]:
            z = set(X) & set(Y)
            for i in range(len(X)-1):
                res.add(tuple(sorted([X[i],X[i+1]])))
                if X[i+1] in z:
                    break
            for i in range(len(Y)-1):
                res.add(tuple(sorted([Y[i],Y[i+1]])))
                if X[i+1] in z:
                    break
            res.add(tuple(sorted([x, y])))
        else:
            self.parents[y] = x

N, E = map(int, input().split())
tree = UnionFind(N)
res = set()
for _ in range(E):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    tree.union(x,y,res)

print(E - len(res))

Submission status: Runtime Error

Solution code:

def solve(pos):
  for i in range(m):
    if line[pos][i] == 1 and reach[i] == 0:
      reach[i] = 1
      solve(i)
  return

n, m = list(map(int, input().split()))
line = [[0]*n for i in range(n)]
ms = []
for i in range(m):
  a, b = list(map(int, input().split()))
  line[a-1][b-1]=1
  line[b-1][a-1]=1
  ms.append([a, b])
  
ans = 0
for i in range(m):
  line[ms[i][0]-1][ms[i][1]-1]=0
  line[ms[i][1]-1][ms[i][0]-1]=0
  reach=[0]*n
  reach[0]=1
  solve(0)
  if 0 in reach:
    ans += 1
  line[ms[i][0]-1][ms[i][1]-1]=1
  line[ms[i][1]-1][ms[i][0]-1]=1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
import itertools

def DFS(g, ab):
  g[ab[0]-1][ab[1]-1] = 0
  g[ab[1]-1][ab[0]-1] = 0
  
  seen = np.zeros((M))
  
  seen[ab[0]-1] = 1
  todo = list([i+1 for i, x in enumerate(g[ab[0]-1]) if(int(x)==1)])
  if(len(todo)!=0):
    while(len(todo)!=0):
      n_todo = list()
      for i in range(len(todo)):
        v = todo[i]
        seen[v-1] = 1
        Tv = list([i+1 for i, x in enumerate(g[v-1]) if((int(x)==1)and(seen[i]==0))])
        for j in range(len(Tv)):
          w = Tv[j]
          if(seen[w-1] == 0):
            seen[w-1] = 1
            n_todo.append(w)
      todo = n_todo
  g[ab[0]-1][ab[1]-1] = 1
  g[ab[1]-1][ab[0]-1] = 1
  return seen

if __name__ == '__main__':
  N, M = [int(x) for x in input().split()]

  G = np.zeros((N,N))
  ab = np.zeros((M,2))
  for i in range(M):
    ab[i][0], ab[i][1] = [int(x) for x in input().split()]    
    G[ab[i][0]-1][ab[i][1]-1] = int(1)
    G[ab[i][1]-1][ab[i][0]-1] = int(1)
    
  count = 0
  for i in range(M):
    se = DFS(G, ab[i])
    if(se[se==1].sum() != N):
      count += 1
  print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
import itertools

def DFS(g, ab):
  g[ab[0]-1][ab[1]-1] = 0
  g[ab[1]-1][ab[0]-1] = 0
  
  seen = np.zeros((M))
  
  seen[ab[0]-1] = 1
  todo = list([i+1 for i, x in enumerate(g[ab[0]-1]) if(int(x)==1)])
  if(len(todo)!=0):
    while(len(todo)!=0):
      n_todo = list()
      for i in range(len(todo)):
        v = todo[i]
        seen[v-1] = 1
        Tv = list([i+1 for i, x in enumerate(g[v-1]) if((int(x)==1)and(seen[i]==0))])
        for j in range(len(Tv)):
          w = Tv[j]
          if(seen[w-1] == 0):
            seen[w-1] = 1
            n_todo.append(w)
      todo = n_todo
  g[ab[0]-1][ab[1]-1] = 1
  g[ab[1]-1][ab[0]-1] = 1
  return seen

if __name__ == '__main__':
  N, M = [int(x) for x in input().split()]

  G = np.zeros((M,M))
  ab = np.zeros((M,2))
  for i in range(M):
    ab[i][0], ab[i][1] = [int(x) for x in input().split()]
    G[ab[i][0]-1][ab[i][1]-1] = int(1)
    G[ab[i][1]-1][ab[i][0]-1] = int(1)
  count = 0
  for i in range(M):
    se = DFS(G, ab[i])
    if(se[se==1].sum() != N):
      count += 1
  print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edges = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    edges[a-1][b-1] = 1
    edges[b-1][a-1] = 1

def dfs(start):
    if visited[start]:
        return
    visited[start] = 1
    for i in range(n):
        if edges[start][i]:
            dfs(i)

ans = m
# edgeを一つづつ見ていく
for i in range(m-1):
    for j in range(i+1, m):
        if not edges[i][j]:
            continue
        # エッジを削除した場合に、連結しているかをdfsで確認
        #   visited: 訪れたかどうかを表す変数
        visited = [0] * n
        edges[i][j] = 0
        edges[j][i] = 0
        dfs(0)
        # お片付け、削除したedgeを元に戻しておく
        edges[i][j] = 1
        edges[j][i] = 1
        # 全て訪れられていたら、そのエッジはなくても非連結にならないので、bridgeではない
        if sum(visited) == n:
            ans -=1

print(ans)

Submission status: Runtime Error

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

def dfs(start):
    if visited[start]:
        return
    visited[start] = 1
    for i in range(n):
        if edges[start][i]:
            dfs(i)

ans = m
# edgeを一つづつ見ていく
for i in range(m-1):
    for j in range(i+1, m):
        if not edges[i][j]:
            continue
        # エッジを削除した場合に、連結しているかをdfsで確認
        #   visited: 訪れたかどうかを表す変数
        visited = [0] * n
        edges[i][j] = 0
        edges[j][i] = 0
        dfs(0)
        # お片付け、削除したedgeを元に戻しておく
        edges[i][j] = 1
        edges[j][i] = 1

        # 全て訪れられていたら、そのエッジはなくても非連結にならないので、bridgeではない
        if sum(visited) == n:
            ans -=1

print(ans)

Submission status: Runtime Error

Solution code:
import collections
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 = collections.deque()
    l = 0
    for nx in g[x]:
        if nx == y:
            continue
        q.append(nx)
        visited[nx] = True
        l += 1

    visited[x] = True

    while l > 0:
        cur = q.pop()
        l -= 1
        if cur == y:
            return True

        for nx in g[cur]:
            if visited[nx]:
                continue
            q.append(nx)
            visited[nx] = True
            l += 1

    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 collections
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 = collections.deque()
    l = 0
    for nx in g[x]:
        if nx == y:
            continue
        q.append(nx)
        l += 1

    visited[x] = True

    while l > 0:
        cur = q.pop()
        l -= 1
        if cur == y:
            return True

        visited[cur] = True
        for nx in g[cur]:
            if visited[nx]:
                continue
            q.append(nx)
            l += 1

    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:
/Users/a13937/Documents/workplace/atcoder-practice/venv/bin/python /Users/a13937/Documents/workplace/atcoder-practice/src/main/scala/abc075/C.py
6 5
1 2
2 3
3 4
4 5
5 6
5

Process finished with exit code 0

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