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:
class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self.parent = [n for n in range(0, N)]
        # グループの深さ
        self.depth = [1] * N
 
    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) # 縮約
        return self.parent[x]
 
    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return
 
        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self.depth[gx] < self.depth[gy]:
            self.parent[gx] = gy
        else:
            self.parent[gy] = gx
            if self.depth[gx] == self.depth[gy]: self.depth[gx] += 1
 
    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)
      
N, M = list(map(int, input().split()))
E = [[int(x)-1 for x in input().split()] for _ in range(M)]

# 各辺について、その辺が存在しない時、aとbが連結になるかをUnion-Findで判定する
ans = 0
for i in range(M):
  uf = UnionFind(N)
  for j, e in enumerate(E):
    if i==j: continue
        
    a, b = e
    uf.unite(a, b)
      
  # i番目の辺を除くすべての辺をつないだあとで、i番目の辺(a, b)がつながるかを判定する
  # つながらないならば、そのi番目の辺は橋である
  a, b = E[i]
  if not uf.is_same_group(a, b):
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
# 全部試す
# 1つあたりO(M)
# O(M^2) = 10^6くらい
import numpy as np
from scipy.sparse.csgraph import dijkstra

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

graph = np.zeros((N+1, N+1))

for a, b in edge:
  graph[a, b] = 1
  
ans = 0
for a, b in edge:
  graph[a, b] = np.inf 
  # directed=False -> 無向グラフ
  dist = dijkstra(graph, indices=a, directed=False)
  if dist[b] == np.inf:
    ans += 1
  graph[a, b] = 1 # 元に戻す
  
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
# グラフの橋という概念を扱う問題 #関節点と似た概念

# 螺旋本の用語を使えば、prenum[p]<lowest[u]となるedge(p,u)が橋

import sys
sys.setrecursionlimit(2**16 - 1)
from collections import defaultdict

INF = 10**9
N, M = list(map(int, input().split()))
G = defaultdict(list)
for _ in range(M):
    a, b = list(map(int, input().split()))
    G[a].append(b)
    G[b].append(a)

# graph Gがdefaultdictで定義された隣接リストであること前提とする。
# n_Vは頂点数
prenum = defaultdict(lambda: None)
parent = defaultdict(lambda: None)
lowest = defaultdict(lambda: None)
timer = 0  # dfsに入った順番を記録(prenum用)
is_visited = defaultdict(lambda: False)  # 木を作るために循環してはいけない
root = 0

# 1のフェーズ、prenumとparent,lowestについて確定していく。


def dfs(cur, prev):  # 次に訪問するノードが以前のノードprevではないことを識別する必要があるので引数がこうなっている
    # 関数に入るときにprenumとparentを確定してく
    global timer
    prenum[cur] = lowest[cur] = timer  # 教科書の説明とは違ってprenumは0スタートだが本質的な違いはない
    timer += 1
    parent[cur] = prev
    is_visited[cur] = True

    # 次のノードに訪問していく
    for nx in G[cur]:  # nxは次に探索すべきノード
        if (not is_visited[nx]):
            dfs(nx, cur)
            lowest[cur] = min(lowest[cur], lowest[nx]
                              )  # 子のlowestの最小値が取得できる
        elif nx != prev:  # 探索済みにつながる木以外の経路 いわゆるback-edge
            # back-edge先のノードの方とどっちが小さいか比較
            lowest[cur] = min(lowest[cur], prenum[nx])


dfs(1, None)

# 2のフェーズ bredgeを見つけていく
# 螺旋本の用語を使えば、prenum[p]<lowest[u]となるedge(p,u)が橋
ans = 0
for u, p in parent.items():
    if p is None:
        continue
    if prenum[p] < lowest[u]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 以下DFSでやろうとしたけど全然ダメだった奴

import copy
import itertools

# N頂点M辺
N, M = map(int, input().split())

# グラフのリスト　各頂点からどこの頂点に向かって辺が伸びてるかという情報
# 2次元配列初期化
graph_list = [[] for i in range(N)]
a_b_list = []

for i in range(M):
    a, b = map(int, input().split())
    a_b_list.append([a - 1, b - 1])
    graph_list[a - 1].append(b - 1)
    graph_list[b - 1].append(a - 1)

# グラフのDFS
def dfs(i, current, graph_list, visited):

    for j in graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の頂点に移動する
            dfs(i + 1, j, graph_list, visited)

    # 全ての頂点を通ったかどうか判定
    if all(visited):
        return True
    else:
        return False


# 橋の数
count_bridge = 0

for m in range(M):
    graph_list_tmp = copy.deepcopy(graph_list)

    a = a_b_list[m][0]
    b = a_b_list[m][1]

    graph_list_tmp[a].pop(graph_list_tmp[a].index(b))
    graph_list_tmp[b].pop(graph_list_tmp[b].index(a))

    # 頂点を通ったかどうか
    visited = [False] * N
    visited[0] = True
    # 一度でも全ての頂点がTrueになったかどうか
    is_visited_all = False
    result = dfs(0, 0, graph_list_tmp, visited)

    if result != True:
        count_bridge += 1

print(count_bridge)

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
sides = [list(map(int,input().split())) for i in range(M)]

vertex = [[] for i in range(N)]
for side in sides:
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])

# print(vertex)

ans = 0

for side in sides:
    vertex[side[0]-1].remove(side[1])
    vertex[side[1]-1].remove(side[0])
    # print(vertex)
    for i in range(1,N+1):
        a = 1
        check = deque([i])
        fromcheck = {j:0 for j in range(1,N+1)}
        visit = {i}
        while len(check) != 0:
            v = check.popleft()
            for ver in vertex[v-1]:
                if fromcheck[ver] == 0:
                    fromcheck[ver] = 1
                    check.append(ver)
                    visit.add(ver)
            fromcheck[v] = 1
        if visit != {i for i in range(1,N+1)}:
            a = 0
            break
    if a == 0:
        ans += 1
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
sides = [list(map(int,input().split())) for i in range(M)]

vertex = [[] for i in range(N)]
for side in sides:
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])

# print(vertex)

ans = 0

for side in sides:
    vertex[side[0]-1].remove(side[1])
    vertex[side[1]-1].remove(side[0])
    # print(vertex)
    for i in range(1,N+1):
        a = 1
        check = deque([i])
        fromcheck = {j:0 for j in range(1,N+1)}
        visit = {i}
        while len(check) != 0:
            v = check.popleft()
            for ver in vertex[v-1]:
                if fromcheck[ver] == 0:
                    fromcheck[ver] = 1
                    check.append(ver)
                    visit.add(ver)
            fromcheck[v] = 1
        if visit != {i for i in range(1,N+1)}:
            a = 0
            break
    if a == 1:
        ans += 1
    vertex[side[0]-1].append(side[1])
    vertex[side[1]-1].append(side[0])

print(M-ans)

Submission status: Accepted

Solution code:
import math
import bisect
import collections
import itertools
import sys
sys.setrecursionlimit(100000000)
def gcd(a,b):return math.gcd #最大公約数
def lcm(a,b):return (a*b) // math.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: divisors.append(n//i)
    return divisors
def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False 
    return True

N,M=imn()
a = []
b = []
visited = [False for _ in range(N)]
graph = [[False for _ in range(50)] for _ in range(50)]
    
for i in range(M):
    v1,v2 = map(lambda x:int(x)-1, input().split())
    a.append(v1)
    b.append(v2)
    graph[v1][v2] = graph[v2][v1] = True

def dfs(v):
    visited[v] = True
    #print(graph[v])
    for v2 in range(N):
        if graph[v][v2] == False: continue
        if visited[v2]: continue
        dfs(v2)

ans = 0

for i in range(M):
    v1 = a[i]
    v2 = b[i]
    graph[v1][v2] = graph[v2][v1] = False
    
    for i in range(N): visited[i] = False

    dfs(0)
    
    for j in range(N):
        if visited[j] == False:
            ans += 1
            break

    graph[v1][v2] = graph[v2][v1] = True

print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
G = {k:[] for k in range(N)}
for _ in range(M):
  a, b = map(int, input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)


def rel_side(v, G):  # 任意の頂点から、他のすべての頂点を訪問したかどうかを確認する関数
  if all(vis):
    return 1
  r = 0
  for side in G[v]:
    if not vis[side]:
      vis[side] = True
      r += rel_side(side, G)
  return r


bridge = 0
for i in range(N):
  for j, k in enumerate(G[i]):
    vis = [False] * N
    vis[i] = True
    pop1 = G[i].pop(j)
    idx = G[pop1].index(i)
    pop2 = G[pop1].pop(idx)
    if not rel_side(i, G):
      bridge += 1
    # print(vis, rel_side(i, G))
    G[i].insert(j, pop1)
    G[pop1].insert(idx, pop2)
    

print(bridge // 2)

Submission status: Accepted

Solution code:
import sys
import copy

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

V = []
E = []
seen = [False]*N
count = 0

for _ in range(N):
    V.append(set())

for _ in range(M):
    *l, = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0]-1,l[1]-1])

V_copy = copy.deepcopy(V)
seen_copy = copy.deepcopy(seen)

def dfs(node):
    if seen[node]==True:
        return
    seen[node]=True

    for next_node in V[node]:
        dfs(next_node)

for i in range(len(E)):
    V[E[i][1]].remove(E[i][0])
    V[E[i][0]].remove(E[i][1])
    dfs(0)

    if (False in seen)==True:
        count = count + 1
    seen = copy.deepcopy(seen_copy)
    V = copy.deepcopy(V_copy)

print(count)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 S(): return input()


def reach_all(G, N):
    visited = [0] * N
    def dfs(G, v):
        visited[v] = 1
        for next_v in G[v]:
            if visited[next_v]:
                continue
            dfs(G, next_v)
    dfs(G, 0)
    if sum(visited) != N:
        return False
    return True

def main():
    N, M = LI()
    edge = []
    for _ in range(M):
        a, b = LI_()
        edge.append((a, b))

    cnt = 0
    for i in range(M):
        G = [[] for _ in range(N)]
        for j in range(M):
            if i == j:
                continue
            a, b = edge[j]
            G[a].append(b)
            G[b].append(a)
        if not reach_all(G, N):
            cnt += 1
    print(cnt)
main()

Submission status: Accepted

Solution code:
import sys, copy
sys.setrecursionlimit(100)

def g(mat, ind):
  return [k for k in range(len(mat)) if mat[ind][k]==1]

def f(mat, ind, sumi):
  sumi[ind]=1
  linknode=g(mat, ind)
  for j in linknode:
    if sumi[j]==0:
      sumi=f(mat, j, sumi)
  return sumi

N, M=map(int, input().split())
ab=[list(map(int, input().split())) for i in range(M)]
net=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
  net[ab[i][0]][ab[i][1]]=1
  net[ab[i][1]][ab[i][0]]=1
  
counter=0
for i in range(M):
  temp=copy.deepcopy(net)
  temp[ab[i][0]][ab[i][1]]=0
  temp[ab[i][1]][ab[i][0]]=0
  if sum(f(temp, 1, [0]*(N+1)))!=N:
    counter+=1
print(counter)

Submission status: Accepted

Solution code:
import sys
import copy




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

seen = [False]*N
V = []
E = []

def dfs(node):
    global V
    global seen

    if seen[node]==True:
        return
    if not (False in seen):
        return
    seen[node]=True

    for next_node in V[node]:
        dfs(next_node)

    return

for i in range(N):
    V.append(set())
    
for i in range(M):
    *l,  = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0]-1, l[1]-1])

seen_copy = copy.deepcopy(seen)
V_copy    = copy.deepcopy(V)
count = 0
#各辺取り除いて深さ優先探索
for edge in E:
    V[edge[0]].remove(edge[1])
    V[edge[1]].remove(edge[0])

    dfs(0)

    if (False in seen):
        count = count + 1

    seen = copy.deepcopy(seen_copy)
    V    = copy.deepcopy(V_copy)

print(count)

Submission status: Accepted

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = []
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    edges.append((a, b))

def check(x):
    nodes = [[] for i in range(N)]
    for i in range(M):
        # 辺x以外でグラフを構築する
        if i == x:
            continue
        a, b = edges[i]
        nodes[a].append(b)
        nodes[b].append(a)
    # BFSで到達確認
    que = deque([0])
    visited = [0] * N
    while que:
        u = que.popleft()
        if visited[u]:
            continue
        visited[u] = 1
        for v in nodes[u]:
               que.append(v)
    # 全ての辺に到達できたか
    return sum(visited) != N

ans = 0
for x in range(M):
    # 辺xを除いて、到達できなくなる場所があればこの辺は橋
    if check(x):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#union-findの練習だと思ってやる。
n,m=map(int,input().split())
A=[list(map(int,input().split()))for i in range(m)]

#union_find
#find, sunite, same, sizeを実装する。
def find(x):
    #findはrootを返す
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    #xとyの属する集合を合体
    #まずは根をとってくる
    x=find(x)
    y=find(y)
    if x==y:
        return False
    else:
        if par[x]>par[y]:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
def same(x,y):
    #xとyが同じ集合かどうか判定
    return find(x)==find(y)
def size(x):
    return -par[x]
#初期化

c=0
for i in range(m):
    par=[-1]*n
    for j in range(m):
        if i==j:
            r,s=A[j]
            r-=1
            s-=1
        else:
            p,q=A[j]
            p-=1
            q-=1
            unite(p,q)
    if same(r,s)==False:
        c+=1
print(c)

Submission status: Accepted

Solution code:
import sys
import copy


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

V = []
E = []

for i in range(N):
    V.append(set())

seen = []
seen = [False] * N

count = 0
def dfs(node):
    global V
    global seen

    #注目ノードは訪問済みか?
    if seen[node]==True:
        return
    
    seen[node]=True

    for next_node in V[node]:
        dfs(next_node)
    return

for i in range(M):
    *l,  = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)
    E.append([l[0]-1, l[1]-1])



E_copy = copy.deepcopy(E)
V_copy = copy.deepcopy(V)
seen_copy = copy.deepcopy(seen)


for i in range(M):
    e = [E[i][0], E[i][1]]
    
    V[e[0]].remove(e[1])
    V[e[1]].remove(e[0])
    
    dfs(0)
    if (False in seen):
        count = count + 1
    seen = [False] * N
    V = copy.deepcopy(V_copy)
   
print(count)

Submission status: Accepted

Solution code:
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
ab = map(int, sys.stdin.read().split())
ab = zip(*[ab] * 2)
graph = [set() for _ in range(n+1)]
for a, b in ab:
    graph[a].add(b)
    graph[b].add(a)

def main():
    que = set()
    for i in range(1, n+1):
        if len(graph[i]) == 1:
            que.add(i)
    res = len(que)
    while que:
        x = que.pop()
        y = graph[x].pop()
        graph[y] -= set([x])
        l = len(graph[y])
        if l == 0:
            que -= set([y])
            res -= 1
        elif l == 1:
            que.add(y)
            res += 1

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
N, M = map(int, readline().split())
graph = [0 for i in range(N)]
ab = []
for i in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    ab.append([a, b])
    graph[a] |= 1 << b
    graph[b] |= 1 << a

all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (not graph[v] >> u & 1) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use

ans = 0
for a, b in ab:
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
    if rec(0, 0) != all_use:
        ans += 1
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [0 for i in range(N)]
ab = []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ab.append([a, b])
    graph[a] |= 1 << b
    graph[b] |= 1 << a
all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (not graph[v] >> u & 1) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use

ans = 0
for a, b in ab:
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
    if rec(0, 0) != all_use:
        ans += 1
    graph[a] ^= 1 << b
    graph[b] ^= 1 << a
print(ans)

Submission status: Accepted

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

all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (not graph[u][v]) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use

ans = 0
for a, b in ab:
    graph[a][b] = graph[b][a] = False
    if rec(0, 0) != all_use:
        ans += 1
    graph[a][b] = graph[b][a] = True
print(ans)

Submission status: Accepted

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

all_use = (1 << N) - 1


def rec(v, use):
    use |= 1 << v
    for u in range(N):
        if (u not in graph[v]) or (use >> u) & 1:
            continue
        use |= rec(u, use)
    return use


ans = 0
for a, b in zip(alst, blst):
    graph[a].remove(b)
    graph[b].remove(a)
    if rec(0, 0) != all_use:
        ans += 1
    graph[a].append(b)
    graph[b].append(a)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())                                         # N:ノード数、M:エッジ数
visited = [False for i in range(N)]                                     # ノードの訪問済みフラグ
edges = [[i-1 for i in map(int,input().split())] for j in range(M)]     # エッジ情報のインプット
graph = [[False for i in range(N)] for j in range(N)]                   # 接続行列の入れ物

# 各エッジについて、情報を接続行列に埋め込む
for edge in edges:
    graph[edge[0]][edge[1]] = True
    graph[edge[1]][edge[0]] = True

# dfs:ノードvについて、エッジで接続した未訪問のノードを深いほうから訪問(LIFO)
def dfs(v):
    queue = [v]
    while len(queue) != 0:
        now = queue.pop()
        visited[now] = True
        for next in range(N):
            if graph[now][next] == False:continue
            if visited[next] == True:continue
            queue.append(next)

ans = 0

# 各エッジを取り除いたとき、dfsして未訪問のノードが残っていれば、そのエッジは橋
for i in range(M):
    graph[edges[i][0]][edges[i][1]] = False
    graph[edges[i][1]][edges[i][0]] = False

    for j in range(N):
        visited[j] = False

    dfs(0)

    bridge = False
    for j in range(N):
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1

    graph[edges[i][0]][edges[i][1]] = True
    graph[edges[i][1]][edges[i][0]] = True

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())                                         # N:ノード数、M:エッジ数
visited = [False for i in range(N)]                                     # ノードの訪問済みフラグ
edges = [[i-1 for i in map(int,input().split())] for j in range(M)]     # エッジ情報のインプット
graph = [[False for i in range(N)] for j in range(N)]                   # 接続行列の入れ物

# 各エッジについて、情報を接続行列に埋め込む
for edge in edges:
    graph[edge[0]][edge[1]] = True
    graph[edge[1]][edge[0]] = True

# dfs:ノードvについて、エッジで接続した未訪問のノードを即時訪問する(再帰処理)
def dfs(v):
    queue = [v]
    while len(queue) != 0:
        now = queue.pop(0)
        visited[now] = True
        for next in range(N):
            if graph[now][next] == False:continue
            if visited[next] == True:continue
            queue.append(next)

ans = 0

# 各エッジを取り除いたとき、dfsして未訪問のノードが残っていれば、そのエッジは橋
for i in range(M):
    graph[edges[i][0]][edges[i][1]] = False
    graph[edges[i][1]][edges[i][0]] = False

    for j in range(N):
        visited[j] = False

    dfs(0)

    bridge = False
    for j in range(N):
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1

    graph[edges[i][0]][edges[i][1]] = True
    graph[edges[i][1]][edges[i][0]] = True

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())                                         # N:ノード数、M:エッジ数
visited = [False for i in range(N)]                                     # ノードの訪問済みフラグ
edges = [[i-1 for i in map(int,input().split())] for j in range(M)]     # エッジ情報のインプット
graph = [[False for i in range(N)] for j in range(N)]                   # 接続行列の入れ物

# 各エッジについて、情報を接続行列に埋め込む
for edge in edges:
    graph[edge[0]][edge[1]] = True
    graph[edge[1]][edge[0]] = True

# dfs:ノードvについて、エッジで接続した未訪問のノードを即時訪問する(再帰処理)
def dfs(v):
    visited[v] = True
    for next in range(N):
        if graph[v][next] == False:continue
        if visited[next] == True:continue
        dfs(next)

ans = 0

# 各エッジを取り除いたとき、dfsして未訪問のノードが残っていれば、そのエッジは橋
for i in range(M):
    graph[edges[i][0]][edges[i][1]] = False
    graph[edges[i][1]][edges[i][0]] = False

    for j in range(N):
        visited[j] = False

    dfs(0)

    bridge = False
    for j in range(N):
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1

    graph[edges[i][0]][edges[i][1]] = True
    graph[edges[i][1]][edges[i][0]] = True

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
n,m=map(int,input().split())
es=[[[] for j in range(n)] for i in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for j in range(m):
        if i!=j:
            es[j][a].append(b)
            es[j][b].append(a)
sw = [[True for i in range(n)] for i in range(m)]# 頂点0とのパスが存在すればFalse, 存在しないならTrue と定義する
def dfs(v,k):
    sw[k][v] = False
    for i in es[k][v]:
        if sw[k][i]:
            dfs(i,k)
for i in range(m):
    dfs(0,i)
ans=0
for j in range(m):
    for i in range(n):
        if sw[j][i]:
            ans+=1
            break
print(ans)

Submission status: Accepted

Solution code:
def dfs(graph, visited, edge):
    visited[edge] = True

    for i in range(n):
        if graph[edge][i] == 1 and visited[i] == False:
            dfs(graph, visited, i)

    if sum(visited) == n: return True
    else: return False


n, m = map(int, input().split())
input_list = []
for i in range(m):
    input_list.append(list(map(int, input().split())))
    
cnt = 0
for skip in range(m):
    graph = [[0]*n for _ in range(n)]

    for stage in range(m):
        if stage == skip:
            continue

        i, j = input_list[stage]
        graph[i-1][j-1] = 1
        graph[j-1][i-1] = 1

    visited = [False for _ in range(n)]

    cnt += dfs(graph, visited, 0)        

print(m - cnt)

Submission status: Accepted

Solution code:
import copy

n, m = map(int, input().split())
Adj_dict_all = {} 
Input_ab_list = []

for i in range(n):
    new = {i+1: []}
    Adj_dict_all.update(new)

# Input + making Adjcency list
for _ in range(m):
    a, b = map(int, input().split())
    Adj_dict_all[a].append(b)
    Adj_dict_all[b].append(a)
    Input_ab_list.append((a,b))

# DFSで求めていく
def Connection(Adj_dict = {}, start = 1, Visited = [False]*n):

    if Visited[start-1]:
        return
    
    # 対象のnodeをVisitedに追加
    Visited[start-1] = True
    
    for node in Adj_dict[start]:
        if Visited[node-1] == False:
            Connection(Adj_dict, node, Visited)
    
    return

ans = 0

# loop for delete each bridge
for i in range(m):
    
    del_a = Input_ab_list[i][0]
    del_b = Input_ab_list[i][1]

    # delete one bridge -> Adj_dict
    Adj_dict = copy.deepcopy(Adj_dict_all)
    Adj_dict[del_a].remove(del_b)
    Adj_dict[del_b].remove(del_a)

    Visited=[False]*n
    Connection(Adj_dict, 1, Visited)

    # check connection
    if not all(Visited):
        ans += 1    

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split(' '))
AB = [list(map(int, input().split(' '))) for i in range(m)]
ans = 0
for X in range(m):
    graph = [[] for i in range(n+1)]
    for i in range(m):
        if i != X:
            [a,b] = AB[i]
            graph[a].append(b)
            graph[b].append(a)
    x = deque([1])
    visited = [0]*(n+1)
    while x:
        q = x.popleft()
        visited[q] = 1
        for i in graph[q]:
            if visited[i] == 0:
                x.append(i)
    for i in range(1,n+1):
        if visited[i] != 1:
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:

def main():
    N, M = list(map(int, input().split()))
    AB = []
    for _ in range(M):
        a, b = list(map(int, input().split()))
        AB.append([a-1, b-1])

    # グラフを表現する（辺のある・なし）
    graph = []
    for _ in range(N):
        graph.append([False] * N)

    for a, b in AB:
        graph[a][b] = True
        graph[b][a] = True
        
    visited = [False] * N

    def dfs(v):
        """v（頂点）からスタートする"""

        # 到達済みだったらreturn
        if visited[v]:
            return

        # 到達した印
        visited[v] = True

        # そのさきへ（vと繋がっている）
        edges = graph[v]
        for i, e in enumerate(edges):
            if e:
                dfs(i)

        return


    ans = 0
        
    # 辺を一つずつ消してみて、橋かどうかを調べる
    for a, b in AB:
        graph[a][b] = False
        graph[b][a] = False

        visited = [False] * N
        dfs(0)
        
        # 全てTrueというわけではない（Falseが一つでもある場合）
        if not all(visited):
            ans += 1

        graph[a][b] = True
        graph[b][a] = True

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

for edge_i in edges:
  check_list = [i for i in range(n)]
  for edge_j in edges:
    if edge_i != edge_j:
      check_list = [check_list[edge_j[0]-1] if check_list[i]==check_list[edge_j[1]-1] else check_list[i] for i in range(n)]
  if len(set(check_list))!=1:ans += 1
      
print(ans)

Submission status: Accepted

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

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

c=-1
s=0
while(True):
    c+=1
    if(c==N):
        break
    if S[c] == 1 :
        for i in range(N):
            if MAP[c][i] == 1 :
                MAP[c][i] = 0
                MAP[i][c] = 0
                S[c]-=1
                S[i]-=1
                s+=1
                c=-1
                break

print(s)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
 
 
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
 
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
 
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
def C(x):
    U=UnionFind(n)
    for i in range(m):
        if i==x :
            continue
        U.unite(ab[i][0]-1, ab[i][1]-1)
    for i in range(n):
        for j in range(n):
            if not U.same(i, j):
                return False
    return True
ans=0
for y in range(m):
    if not C(y):
        ans+=1
print(ans)

Submission status: Accepted

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

ORD = [0] * (N+1)
LOW = [0] * (N+1)
used = [False] * (N+1)
bridge = []

def dfs(idx, k, parent):
    global E,ORD,LOW,used,bridge
    used[idx] = True
    ORD[idx] = k
    LOW[idx] = k
    for to in E[idx]:
        if not used[to]:
            k = dfs(to, k+1, idx)
            LOW[idx] = min(LOW[idx], LOW[to])
            if ORD[idx] < LOW[to]:
                bridge.append(sorted([idx,to]))
        elif to != parent:
            LOW[idx] = min(LOW[idx], ORD[to])
    return k

dfs(1, 1, 0)
print(len(bridge))

#print(bridge)
#print(ORD)
#print(LOW)
#print(used)
#print(E)