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: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a - 1, b - 1))
ans = 0
for i in range(M):
    to = [[] for _ in range(N)]
    for j, (a, b) in enumerate(AB):
        if i != j:
            to[a].append(b)
            to[b].append(a)
    visited = [False] * N
    q = deque()
    q.append(0)
    visited[0] = True
    while len(q):
        a = q.pop()
        for b in to[a]:
            if not visited[b]:
                q.append(b)
                visited[b] = True
    if not all(visited):
        ans += 1
print(ans)

Submission status: Accepted

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

def create_dict(ab_list):
    d = {}
    for a,b in ab_list:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
            
    return d

# def check():
cnt = 0

for i in range(M):
#     print("i:",i)
    tmp_ab_list = ab_list[:i] + ab_list[i+1:]

    d = create_dict(tmp_ab_list)
#     print("d:",d)
    connected = [0 for _ in range(N+1)]

    def write_connected(a):
#         print(a)
        if connected[a] == 0:
            connected[a] = 1
            if a in d:
                for next_a in d[a]:
                    write_connected(next_a)

    write_connected(1)

#     print(connected)
    if sum(connected) < N:
        cnt += 1
#     return cnt

print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#幅優先探索（BFS）を利用
# 頂点と辺の数を入力する
N, M = map(int, input().split())
# 隣接リストを作成する
list_adjlist = [[] for _ in range(N + 1)]
# 辺のリストを作成する
list_edge = []
# 辺を入力し、隣接リストおよび辺のリストに格納する
for _ in range(M):
    a, b = map(int, input().split())
    list_edge.append((a, b))
    list_adjlist[a].append(b)
    list_adjlist[b].append(a)

def FIFO(list_FIFO, node):
    if node != None:
        list_FIFO.append(node)
        return None
    return list_FIFO.pop(0)

# 橋の総数（all_bridge）を初期化する
all_bridge = 0

# uv間の辺がなくても、uからvへたどり着けるか探索
for u, v in list_edge:
    # uv間の辺が橋かどうか（uv_bridge）を初期化する（初期状態：1＝橋である）
    uv_bridge = 1
    # FIFOキューを初期化する
    list_FIFO = []
    # FIFOキューに入れたことのある点かどうかをチェックするリスト（list_check）を初期化する
    list_check = [False] * (N + 1)
    # FIFOキューにuを追加する
    FIFO(list_FIFO, u)
    # uをFIFOキューに入れた点としてチェックする
    list_check[u] = True
    # FIFOキューが空でない、かつvにたどり着いていない限り、幅優先探索
    while list_FIFO != [] and list_FIFO[-1] != v:
        # FIFOキューから点（node）を取り出す
        node = FIFO(list_FIFO, None)
        # nodeの隣接点（adjnode）について繰り返す
        for adjnode in list_adjlist[node]:
            # adjnodeがFIFOキューに入れたことのある点だった場合
            if list_check[adjnode]:
                # 以降の処理は行わずに次の隣接点に移る
                continue
            # adjnodeがvだった場合
            if adjnode == v:
                # nodeがuでない場合
                if node != u:  
                    # uv_bridgeを更新する（0＝橋でない）
                    uv_bridge = 0
                    # FIFOキューにadjnodeを追加する
                    FIFO(list_FIFO, adjnode)
                    # 繰り返しを終了する
                    break
            # adjnodeがv出ない場合
            else:
                # FIFOキューにadjnodeを追加する
                FIFO(list_FIFO, adjnode)
                # adjnodeをFIFOキューに入れた点としてチェックする
                list_check[adjnode] = True
    # all_bridgeにuv_bridgeを加える
    all_bridge += uv_bridge
                
# all_bridgeを出力する
print(all_bridge)

Submission status: Accepted

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

ans = 0

for i in range(M):
    brid = [[] for _ in range(N)]
    check = [0] * N
    for j in range(M):
        if j != i:
            brid[a[j]-1].append(b[j]-1)
            brid[b[j]-1].append(a[j]-1)
#    print(brid)


    stack = []
    for j in range(len(brid[0])):
        stack.append(brid[0][j])
        check[brid[0][j]] == 1
    
    while len(stack) != 0 :
        x = stack.pop(-1)
        for j in range(len(brid[x])):
            if check[brid[x][j]] == 0:
                stack.append(brid[x][j])
                check[brid[x][j]] = 1
    
#    print(check)

    if check.count(1) != len(check):
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))
A = np.array(A) - 1
B = np.array(B) - 1


def is_bridge(i):
    a = np.concatenate([A[:i], A[i + 1:]])
    b = np.concatenate([B[:i], B[i + 1:]])
    graph = csr_matrix(([True] * (M - 1), (a, b)), shape=(N, N))
    _, components = connected_components(graph, directed=False)
    return components.max() >= 1


ans = 0
for i in range(M):
    ans += is_bridge(i)
print(ans)

Submission status: Accepted

Solution code:
import queue

N, M = map(int, input().split())
adjacent = [[False] * N for i in range(N)]
bridges = []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    bridges.append((a, b))
    adjacent[a][b] = adjacent[b][a] = True

ans = 0
for a, b in bridges:
    adjacent[a][b] = adjacent[b][a] = False
    visited = [0] * N

    visited[0] = 1
    q = queue.Queue()
    q.put(0)
    while not q.empty():
        u = q.get()
        for v in range(N):
            if not adjacent[u][v]:
                continue
            if visited[v] == 1:
                continue
            visited[v] = 1
            q.put(v)

    if sum(visited) < N:
        ans += 1
    adjacent[a][b] = adjacent[b][a] = True
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import*;N,M,*A=map(int,open(0).read().split());g=csr_matrix(([1]*M,(A[::2],A[1::2])),shape=(N+1,N+1)).tolil();c=0
for a,b in zip(*g.nonzero()):g[a,b]=0;n,_=csgraph.connected_components(g);c+=n!=2;g[a,b]=1
print(c)

Submission status: Accepted

Solution code:
from scipy.sparse import *;N,M,*A=map(int,open(0).read().split());g=csr_matrix(([1]*M,(A[::2],A[1::2])),shape=(N+1,N+1)).tolil();c=0
for a,b in zip(*g.nonzero()):
 g[a,b]=0;n,_=csgraph.connected_components(g);c+=n!=2;g[a,b]=1
print(c)

Submission status: Accepted

Solution code:
from scipy.sparse import *;from scipy.sparse.csgraph import connected_components;N,M=map(int,input().split());g=lil_matrix((N,N))
for _ in [0]*M:
  a,b=list(map(int,input().split()));g[a-1,b-1]=1
c=0
for a,b in zip(*g.nonzero()):
  g[a,b]=0;c+=connected_components(g,return_labels=False)!=1;g[a,b]=1
print(c)

Submission status: Accepted

Solution code:
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import connected_components

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

g = lil_matrix((N, N))
for _ in range(M):
  a, b = list(map(int, input().split()))
  g[a - 1, b - 1] = 1

c = 0
for a, b in zip(*g.nonzero()):
  g[a, b] = 0
  c += connected_components(g, return_labels=False) != 1
  g[a, b] = 1
  
print(c)

Submission status: Accepted

Solution code:

class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
n,m = map(int,input().split())
arr = [[0 for i in range(n)] for j in range(n)]
e = set()
ans = 0
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    e.add((a,b))

for el in e:
    tree = uf_tree(n)
    for key in e:
        if key != el:
            tree.unite(key[0],key[1])
    if tree.indep() > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n,m = map(int,input().split())
edge = [[] for _ in range(n)]
del_edge = []
cnt = 0

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    del_edge.append((a,b))

def find(s,de):
    visited = [False] * n
    visited[s] = True
    que = []
    for e in edge[s]:
        if s in de and e in de:
            continue
        heappush(que,e)
    while que:
        v = heappop(que)
        if visited[v]:
            continue
        visited[v] = True
        for vtx in edge[v]:
            if v in de and vtx in de:
                continue
            hq = vtx
            heappush(que,hq)
    if False in visited:
        return 1
    else:
        return 0

for i in range(m):
    tmp = del_edge[i]
    cnt += find(0,tmp)

print(cnt)

Submission status: Accepted

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

g = [[0] * N for _ in range(N)]
for i, j in l:
  g[i - 1][j - 1] = 1
  g[j - 1][i - 1] = 1

def dfs(n):
  v[n - 1] = 1
  for n2 in range(1, N + 1):
    if g[n - 1][n2 - 1] == 1 and v[n2 - 1] == 0:
      dfs(n2)

r = 0
for i, j in l:
  g[i - 1][j - 1] = 0
  g[j - 1][i - 1] = 0
  
  v = [0] * N
  dfs(i)
  if sum(v) != N:
    r += 1
  
  g[i - 1][j - 1] = 1
  g[j - 1][i - 1] = 1
  
print(r)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
edges = []

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b))

ans = 0
for removeEdge in range(M):
    confilm = [False for _ in range(N)]
    que = deque([])
    que.append(0)

    while que:
        now = que.popleft()
        confilm[now] = True
        for i, (a, b) in enumerate(edges):
            if i == removeEdge:
                continue
            if a == now:
                if not confilm[b]:
                    que.append(b)
            if b == now:
                if not confilm[a]:
                    que.append(a)
    if False in confilm:
        ans += 1

print(ans)

Submission status: Accepted

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

leafList = set([])
ans = 0
while True:
    isAll = True
    for v in range(N):
        if v in leafList:
            continue
        edgeCount = 0
        for to in edges[v]:
            if to in leafList:
                continue
            edgeCount += 1
        if edgeCount == 1:
            isAll = False
            ans += 1
            leafList.add(v)
    if isAll:
        break
print(ans)

Submission status: Accepted

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

def dfs(x):
    global v
    v.append(x)
    for k in range(n):
        global i
        if ab[x][k] == 1 and not k in v:
            dfs(k)
count = 0
for i in range(m):
    ab[eda[i][0]][eda[i][1]] = 0
    ab[eda[i][1]][eda[i][0]] = 0
    v = []
    dfs(0)
    if len(v) != n:
        count += 1
    ab[eda[i][0]][eda[i][1]] = 1
    ab[eda[i][1]][eda[i][0]] = 1
print(count)

Submission status: Accepted

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

paths = [[0] * (N + 1) for _ in range(N + 1)]

edges = []
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    paths[a][b] = 1
    paths[b][a] = 1
    edges.append((a, b))


class UF:
    def __init__(self, v):
        self.parent = None
        self.val = v

    @property
    def root(self):
        if not self.parent:
            return self
        return self.parent.root

    def __str__(self):
        if self.parent:
            return str(self.val) + ' ' + str(self.parent.val)
        return str(self.val) + ' None'


def merge(u1, u2):
    r1 = u1.root
    r2 = u2.root
    if r1 == r2:
        return
    r1.parent = r2


def chk(a, b):
    nodes = [UF(i) for i in range(N + 1)]
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            if paths[i][j]:
                merge(nodes[i], nodes[j])
    return int(nodes[a].root != nodes[b].root)


ans = 0
for e in edges:
    paths[e[0]][e[1]] = 0
    paths[e[1]][e[0]] = 0
    ans += chk(e[0], e[1])
    paths[e[0]][e[1]] = 1
    paths[e[1]][e[0]] = 1
print(ans)

Submission status: Accepted

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

def rec(now, i):
    seen[now] = True
    for e in edges[now]:
        if e[1] == i:
            continue
        if seen[e[0]]:
            continue
        rec(e[0], i)


ans = 0
for i in range(m):
    seen = [False for i in range(n)]
    rec(0, i)
    if False in seen:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
raw = []
ans = 0
for i in range(m):
  raw.append(list(map(lambda x:int(x)-1,input().split())))
for i in range(m):
  ab = [[] for _ in range(n)]
  for mi in range(m):
    if mi != i:
      try:
        here = raw[mi]
        ab[here[0]].append(here[1])
        ab[here[1]].append(here[0])
      except:
        print(ab,here,here[0],here[1])
  for ni in range(n):
    now = [ni]
    rest = [j for j in range(n)]
    for _ in range(50):
      nex = []
      for x in now:
        if x in rest:
          rest.remove(x)
        nex += ab[x]
      now = list(set(nex))
      if rest == []:
        break
    else:
      continue
    break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def c_bridge(N, M, Edges):
    def dfs(v):
        is_visited[v] = True  # 現在の頂点を訪問済にする
        for v2 in range(N):
            if not graph[v][v2] or is_visited[v2]:
                continue  # 頂点v2に行けないか、行く必要がない
            dfs(v2)

    graph = [[False for _ in range(N)] for _ in range(N)]
    for a, b in Edges:
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True

    # 各辺は橋か？ グラフからその辺を取り除いて、グラフが連結かを判定
    ans = 0
    for a, b in Edges:
        # 辺を取り除く
        graph[a - 1][b - 1] = False
        graph[b - 1][a - 1] = False

        # すべての辺を未訪問として初期化
        is_visited = [False for _ in range(N)]
        # 全頂点に到達できなければ、除いた辺は橋である
        dfs(0)
        ans += 1 if not all(is_visited) else 0

        # 辺を復元
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    return ans

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(c_bridge(N, M, Edges))

Submission status: Accepted

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(M):
    # 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: Accepted

Solution code:
import queue

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

for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
    A.append(a)
    B.append(b)

def bfs(ab, n, na, nb):
    ok = [False for i in range(n)]
    q = queue.Queue()
    q.put(0)
    while not q.empty():
        f = q.get()
        ok[f] = True
        for c in ab[f]:
            if (f==na and c==nb) or (f==nb and c==na):
                continue
            if ok[c] == False:
                q.put(c)
    
    flag = True
    for i in ok:
        flag &= i
    return flag

ans = 0
for a, b in zip(A, B):
    if bfs(ab, n, a, b) == False:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())

es = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]

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

    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        else:
            self.parent[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        self.count += 1


ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(es):
        if i == j:
            continue # 一つ辺を外す
        if uf.is_same(a, b):
            continue # 現時点で繋がってるのでOK
        uf.unite(a, b)
    x, y = es[i]
    if not uf.is_same(x, y):
        ans += 1 # ある辺を外した時にその辺の両端のノードが同じ集合でないと繋がってないので橋といえる

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

def connected_num(N, G):
    # ノード0から行けるノードの数が全体のノード数に一致するか
    visited = [0] * N
    stack = [0]
    while(len(stack) > 0):
        n = stack.pop()
        if visited[n] == 0:
            stack += G[n]
            visited[n] = 1
    return sum(visited) != N
def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    counter = 0
    for j in range(M):
        G = [[] for _ in range(N)]
        for i in list(range(j))+list(range(j+1, M)):
            G[a[i]-1].append(b[i]-1)
            G[b[i]-1].append(a[i]-1)
        if connected_num(N, G):
            counter += 1
    print(counter)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(V,E):
    s[V-1]=1
    for i in Ren[V-1]:
        if E!={V,i} and s[i-1]==0:dfs(i,E)
N,M=map(int,input().split())
Edge=[list(map(int,input().split())) for i in range(M)]
Ren=[[] for i in range(N)]
for a,b in Edge:
    Ren[a-1].append(b)
    Ren[b-1].append(a)
ans=0
for i in Edge:
    s=[0]*N
    dfs(1,set(i))
    if 0 in s:ans+=1
print(ans)

Submission status: Accepted

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


def solve(N, M, edges):
    def is_connected(es):
        e = [[False]*(N+1) for _ in range(N+1)]
        for a, b in es:
            e[a][b] = True
            e[b][a] = True

        visited = [False]*(N+1)
        s = [1]
        while len(s) > 0:
            v = s.pop()
            visited[v] = True
            for i in range(1, N+1):
                if e[v][i] and not visited[i]:
                    s.append(i)

        for v in range(1, N+1):
            if not visited[v]:
                return False

        return True

    bridge = 0
    for i in range(M):
        if not is_connected(edges[:i] + edges[i+1:]):
            bridge += 1

    return bridge


def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        a, b = map(int, input().split())
        edges.append((a, b))
    print(solve(N, M, edges))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

E = sorted(E)

P = -1

def unionFind(E):
    parent = [i for i in range(N+1)]
    def root(a):
        p = a
        while parent[p] != p:
            p = parent[p]
        parent[a] = p
        return p
        
    for a, b in E:
        pa = root(a)
        pb = root(b)
        if pa < pb:
            parent[pb] = pa
        elif pa > pb:
            parent[pa] = pb

    for i in range(1, N+1):
        root(i)
    return max(parent)

def main():
    bridge = 0
    if M == 1:
        print(1)
    else:
        for i in range(0, M):
            if unionFind(E[:i]+E[i+1:]) != 1:
                bridge += 1
        print(bridge)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    edges = defaultdict(list)
    for f_, t_ in zip(a, b):
        edges[f_-1].append(t_-1)
        edges[t_-1].append(f_-1)

    visited = [False] * N

    def dfs(f_, pre):
        if visited[f_] is True:
            return True

        visited[f_] = True
        for t_ in edges[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_)
        return

    counter = 0
    for f_, t_ in zip(a, b):
        edges[f_-1].remove(t_-1)
        edges[t_-1].remove(f_-1)
        visited = [False] * N
        dfs(0, -1)
        if all(visited) is False:
            counter += 1
        edges[f_-1].append(t_-1)
        edges[t_-1].append(f_-1)
    print(counter)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for a,b in edges:
    graph[a][b] = 0
    graph[b][a] = 0

    visited = [False] * N
    visited[0] = True
    q = [i for i in range(N) if graph[0][i]]

    while q:
        r = q.pop(0)
        visited[r] = True
        for i in range(N):
            if graph[r][i] and not visited[i]:
                q.append(i)

    if False in visited:
        ans += 1

    graph[a][b] = 1
    graph[b][a] = 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]*m;b=[0]*m
for i in range(m):a[i],b[i]=map(int,input().split())

def check(l):
    r=[False]*(n+1)
    r[0]=True
    r[1]=True
    c=1
    while c>0:
        c=0
        for i in l:
            if r[a[i]]^r[b[i]]:r[a[i]]=True;r[b[i]]=True;c+=1
    if all(r):return True
    else: return False
c=0
for i in range(m):
    if not check(list(range(i))+list(range(i+1,m))):c+=1
print(c)

Submission status: Accepted

Solution code:
def BFS(L):
    Visit=[]
    now=[]

    L_temp=L.copy()
    Visit.extend(L_temp[0])
    now.extend(L_temp[0])

    L_temp.remove(L_temp[0])

    # L_temp.pop(L_t)
    l_n=0
    while 0 < len(L_temp) and 0 < len(now):
        now_t=now[0]
#         print('======')
#         print(Visit)
#         print(L_temp)
        l=L_temp[l_n]
        l_n+=1
#         print(L_temp)
#         print(now)
#         print(l)
        for t_n in range(len(l)):
            t_n_r = 1-t_n
            if now_t == l[t_n] :
                if l[t_n_r] not in Visit:
                    Visit.append(l[t_n_r])
                now.append(l[t_n_r])
                L_temp.remove(l)
                l_n=0

        if l_n == len(L_temp):
            now=now[1:]
            l_n=0   
    
    return(Visit)

N,M=[int(x) for x in input().split()]
L=[]
for i in range(M):
    L.append([int(x) for x in input().split()])

# A=[int(x) for x in read_input().split()]
# B=[int(x) for x in read_input().split()]

ans=0
for l in range(len(L)):
    L_temp=L.copy()
    L_temp.pop(l)
    
    visit=BFS(L_temp)
    len_visit=len(visit)
    
    if len_visit!=N:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import copy

n, m = map(int, input().split())
graph = {i + 1: [] for i in range(n)}
edge = []
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    edge.append([a, b])
count = 0
for i in range(m):
    copy_graph = copy.deepcopy(graph)
    a, b = edge[i][0], edge[i][1]
    copy_graph[a].remove(b)
    copy_graph[b].remove(a)
    checked = set()
    check = [a]
    while check:
        test = check.pop(0)
        for j in copy_graph[test]:
            if j not in checked:
                check.append(j)
        checked |= {test,}
    if b not in checked:
        count += 1
print(count)

Submission status: Accepted

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


ans = 0
for l in line:
    a, b = l
    qs = [a]
    checked = [False for _ in range(N)]
    checked[b] = True
    ok = False
    #print(a, b)
    first = True
    while qs:
        #print(qs)
        qqs = []
        for q in qs:
            checked[q] = True
            for k in graph[q]:
                #print(k)
                if k == b and first:
                    first = False
                elif k == b:
                    ok = True
                    break
                if not checked[k]:
                    qqs.append(k)
        qs = qqs
    if not ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
def f(List,n):
    D[n]=1
    if List[n]==[]:return
    else:
        for i in List[n]:
            if D[i]==1:pass
            else:f(List,i)
    
N,M=map(int,input().split())
L=deque([[] for _ in range(N)]for _ in range(M))
for i in range(M):
    a,b=map(int,input().split())
    for j in range(M):
        if i==j:pass
        else:
            L[j][a-1].append(b-1)
            L[j][b-1].append(a-1)

ans=0
for k in range(M):
    List=L.popleft()
    D=defaultdict(int)
    f(List,0)
    judge=0
    for l in range(N):
        if D[l]==0:judge+=1
        else:pass
    if judge!=0:ans+=1
print(ans)