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:
n, m = map(int, input().split())
g = [[False] * n for _ in range(n)]
visited = [False] * n
a = []
b = []
ans = 0


def dfs(v):
    visited[v] = True
    for to in range(n):
        if not g[v][to]:
            continue
        if visited[to]:
            continue
        dfs(to)


for _ in range(m):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    a.append(ai)
    b.append(bi)
    g[ai][bi] = True
    g[bi][ai] = True

for i in range(m):
    g[a[i]][b[i]] = False
    g[b[i]][a[i]] = False
    for j in range(n):
        visited[j] = False
    dfs(0)
    for j in range(n):
        if not visited[j]:
            ans += 1
            break
    g[a[i]][b[i]] = True
    g[b[i]][a[i]] = True

print(ans)

Submission status: Accepted

Solution code:
"""
解説PDFを見ながら実装
https://img.atcoder.jp/abc075/editorial.pdf
"""

def dfs(v, graph, visited, n):
    # 出発点
    visited[v] = True
    for i in range(n):
        # 辺がない
        if graph[v][i] == False:
            continue
        # 訪問済み
        if visited[i] == True:
            continue
        # 辺があったらそこから訪問する
        dfs(i, graph, visited, n)


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

    graph = []
    for _ in range(N):
        row = [False] * N
        graph.append(row)

    A = []
    B = []
    for _ in range(M):
        a, b = list(map(int, input().split()))
        a = a - 1
        b = b - 1
        A.append(a)
        B.append(b)
        graph[a][b] = True
        graph[b][a] = True
    # print(graph)

    ans = 0

    for i in range(M):
        # 辺を削除
        graph[A[i]][B[i]] = False
        graph[B[i]][A[i]] = False

        visited = [False] * N

        # 常に0番目の頂点から出発
        dfs(0, graph, visited, N)

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

        # 辺を戻す
        graph[A[i]][B[i]] = True
        graph[B[i]][A[i]] = True

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bfs(n, t, v):
    for p in t[n]:
        if p not in visited:
            visited.add(p)
            bfs(p, t, v)

ans = 0
for i in range(M):
    t = {i:[] for i in range(1, N+1)}
    visited = set()
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j]
        t[a].append(b)
        t[b].append(a)
    bfs(1, t, visited)
    if len(visited) != N:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
n,m = map(int, input().split())
ls = np.zeros([n,n])
for _ in range(m):
    a, b = map(int, input().split())
    if ls[a-1][b-1] == 0:
        ls[a-1][b-1] = 1
        ls[b-1][a-1] = 1

def dfs(a, visitedls):
    visitedls.append(a)
    for b in range(1,n+1):
        if ls[a-1][b-1] == 1 and b not in visitedls:
            dfs(b, visitedls)

def main():
    ans = 0
    for i in range(n):
        for j in range(n):
            if ls[i][j] == 1:
                ls[i][j] = 0
                visitedls = []
                dfs(i+1, visitedls)
                if len(visitedls) != n:
                    ans += 1
                ls[i][j] = 1
    print(int(ans/2))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,w = map(int,input().split())
l=[list(map(int,input().split())) for i in range(w)]
ans=0
#edge[i] : iから出る道の[重み,行先]の配列
for j in range(w):
    edge = [[] for i in range(n)]
    b=l[:j]+l[j+1:]
    for i in range(w-1):
        x,y = b[i][0],b[i][1]
        x-=1;y-=1
        z=1
        edge[x].append([z,y]) #有向辺
        edge[y].append([z,x]) #有向辺
    if float("inf") in dijkstra_heap(0):
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        # parent[x] < 0 means x is root and abs(parent[x]) == size[x]
        self.parent, self.depth = [-1] * n, [0] * n

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

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

    def unite(self, x, y):
        if self.isSame(x, y):
            return
        x, y = self.find(x), self.find(y)

        if self.depth[x] > self.depth[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.depth[x] == self.depth[y]:
                self.depth[y] += 1

    def numTree(self):
        return sum([1 for p in self.parent if p < 0])


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

ans = 0
for i in range(M):
    U = UnionFind(N)
    for a, b in E[:i] + E[i + 1:]:
        U.unite(a - 1, b - 1)
    if U.numTree() == 2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [set() for i in range(N)]
l = []
for i in range(M):
  a, b = map(int, input().split())
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)
  l.append((a-1, b-1))

ans = M

for i in range(M):
  used = [False] * N
  a, b = l[i]
  edge[a].discard(b)
  edge[b].discard(a)

  stack = [0]
  while stack:
    prev = stack.pop()
    if used[prev]: continue

    used[prev] = True
    for to in edge[prev]:
      stack.append(to)
  
  if all(used): ans -= 1

  edge[a].add(b)
  edge[b].add(a)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)] # par[i]=iとして初期化  ex) par[3]=2 :3の親は2
        self.rank = [0] * (n+1)

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

        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y

        else:
            self.par[y] = x

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m = map(int,input().split())
 
edges = [list(map(int,input().split())) for i in range(m)]
 
ans = 0
 
for i in range(m):
	uf = UnionFind(n)
	for j in range(m):
		if i != j:
			uf.union(edges[j][0]-1,edges[j][1]-1)
 
	c = 0
	for j in range(n):
		if j == uf.find(j):
			c += 1
 
	if c > 1 :
		ans += 1 
print(ans)

Submission status: Accepted

Solution code:
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def dfs(G, v):
	seen[v] += 1
	#print('v :', v)
	
	for nv in G[v]:
		if seen[nv]: continue
		#print('v nv :', v, nv, 'Recursion')
		dfs(G, nv)

N, M = MAP()
A = [MAP() for _ in range(M)]

#print(A)

ans = 0
for i in range(M):
	G = [[] for _ in range(N)]
	for j, m in enumerate(A):
		# i!=jのとき辺を追加しない
		if i != j:
			a, b = m
			G[a-1].append(b-1)
			G[b-1].append(a-1)
		
	seen = [0] * N
	dfs(G, 1)
	#print(i, j, seen)
	
	if sum(seen) != N: ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for y in range(m)]
graph = [[] for x in range(n + 1)]


def dfs(graph, now, a, b):
    visited[now] = True
    for next in graph[now]:
        if (now == a and next == b) or (now == b and next == a):
            continue
        if not visited[next]:
            dfs(graph, next, a, b)
    return visited.count(False) == 1


for a, b in ab_array:
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for a, b in ab_array:
    start = a
    end = b
    visited = [False for x in range(n + 1)]
    now = 1
    next_array = [now]
    while len(next_array) != 0:
        visited[now] = True
        for next in graph[now]:
            if (now == a and next == b) or (now == b and next == a):
                continue
            if not visited[next]:
                next_array.append(next)
        now = next_array.pop()
    if visited.count(False) == 1:
        ans += 1

    # if dfs(graph, 1, a, b):
    #     ans += 1
print(m - ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for y in range(m)]
graph = [[] for x in range(n + 1)]


def dfs(graph, now, a, b):
    visited[now] = True
    for next in graph[now]:
        if (now == a and next == b) or (now == b and next == a):
            continue
        if not visited[next]:
            dfs(graph, next, a, b)
    return visited.count(False) == 1


for a, b in ab_array:
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for a, b in ab_array:
    start = a
    end = b
    visited = [False for x in range(n + 1)]
    if dfs(graph, 1, a, b):
        ans += 1
print(m - ans)

Submission status: Accepted

Solution code:
def dfs(current):
    for maps in Graph[current]:
        if maps in already:
            continue
        else:
            already.append(maps)
            dfs(maps)

n,m = map(int,input().split())
ans = 0
Edges = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    Edges.append((a,b))

for i in range(m):
    egdes = Edges[0:i]+Edges[i+1:]
    Graph = [[] for _ in range(n)]
    for edge in egdes:
        Graph[edge[0]].append(edge[1])
        Graph[edge[1]].append(edge[0])
    already = []
    dfs(0)
    if len(already) != n:
        ans += 1
print(ans)

Submission status: Accepted

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 = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    tmp = edge.pop(i)
    uf = UnionFind(N)
    for j in range(M-1):
        u,t = edge[j][0]-1,edge[j][1]-1
        uf.union(u,t)
        uf.union(t,u)
    if uf.group_count() != 1:
        ans += 1
    edge.insert(i,tmp)
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:
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 = map(int,input().split())
abl = []
for _ in range(m):
    a,b = map(int,input().split())
    abl.append((a,b))

all_uf = UnionFind(n)
for a,b in abl:
    all_uf.union(a-1,b-1)
k = all_uf.group_count()

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for a,b in abl[:i] + abl[i+1:]:
        uf.union(a-1,b-1)
    if k != uf.group_count():
        ans += 1

print(ans)

Submission status: Accepted

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

B = [[] for i in range(n + 1)]

for i in range(m):
    B[A[i][0]].append(A[i][1])
    B[A[i][1]].append(A[i][0])

co = 0
ok = 0
while ok == 0:
    ok = 1
    for i in range(1, n + 1):
        if len(B[i]) == 1:
            ok = 0
            k = B[i][0]
            B[i].remove(k)
            B[k].remove(i)
            co += 1

print(co)

Submission status: Accepted

Solution code:
import copy
def dfs(graph,s):
    S=[s]
    visited=[s]
    while len(S)>0:
        v=S.pop()

        for n in graph[v]:

            if n not in visited:
                S.append(n)
                visited.append(n)
    return len(visited)


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    graph={i+1:[] for i in range(N)}
    E=[]
    for i in range(M):
        a,b=list(map(int,input().split()))
        graph[a].append(b)
        graph[b].append(a)
        E.append((a,b))

    ans=0
    for e in E:
        a,b=e[0],e[1]
        copied=copy.deepcopy(graph)
        copied[a].remove(b)
        copied[b].remove(a)
        if dfs(copied,1)!=N:
            ans+=1
    print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
lab=[]
dn={}
for i in range(M):
    #lab.append(list(map(int,input().split())))
    a,b=map(int,input().split())
    lab.append([a,b])
    if not a in dn:
        dn[a]=[b]
    else:
        dn[a].append(b)
    if not b in dn:
        dn[b]=[a]
    else:
        dn[b].append(a)
ans=0
for i in range(M):
    #dtmp=copy.copy(dn)
    #for dd in dtmp:
    #    if dd[]
    st=[lab[i][0]]
    df={lab[i][0]:1}
    ng=lab[i][1]
    #while st:
    f=0
    for j in range(N):
    #while st:
        if not st:
            break
        ntmp=st.pop()
        if ntmp==ng:
            f=1
            break
        for nc in dn[ntmp]:
            if not nc in df and not (ntmp==lab[i][0] and nc==lab[i][1]):
                st.append(nc)
                df[nc]=1
    if f==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# 方針: N本のそれぞれを抜いた時全ての頂点を探索することができるか判定し、カウントを行う。
import copy
N , M = map(int,input().split())

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

def dfs(now):
    stack = [work_graph[now]]
    while stack:
        next_nodes = stack.pop()
        for next_node in next_nodes:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append(work_graph[next_node])


cnt = 0
for i in range(M):
    work_graph = [[] for _ in range(N)]
    for j in range(M):
        if j == i:
            continue
        work_graph[tmp_list[j][0]].append(tmp_list[j][1])
        work_graph[tmp_list[j][1]].append(tmp_list[j][0])
    visited = [False] * N
    dfs(0)
    if not all(visited):
        cnt += 1
print(cnt)

Submission status: Accepted

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

a_list = []
b_list = []
edge = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a_list.append(a - 1)
    b_list.append(b - 1)
    edge[a - 1][b - 1] = 1
    edge[b - 1][a - 1] = 1

ans = 0
flags = [False] * N

def dfs(v):
    flags[v] = True
    for v2 in [i for i, x in enumerate(edge[v]) if x == 1]:
        if flags[v2]:
            continue
        dfs(v2)

for i in range(M):
    edge[a_list[i]][b_list[i]] = 0
    edge[b_list[i]][a_list[i]] = 0

    flags = [False] * N

    dfs(0)
    ans += 1 if not all(flags) else 0

    edge[a_list[i]][b_list[i]] = 1
    edge[b_list[i]][a_list[i]] = 1

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
N, M = map(int, input().split())
graph = dict()
for i in range(N):
    graph[i] = []
ab = [tuple(map(int, input().split())) for _ in range(M)]

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

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

for a, b in ab:
    graph[a - 1][b - 1] = 1
counter = 0
for a, b in ab:
    g = deepcopy(graph)
    g[a - 1][b - 1] = 0
    g = csr_matrix(g)
    shortest_paths = shortest_path(g, directed=False, method="D")
    if inf in shortest_paths[0]:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
import copy
def dfs(tmp):
  for i in range(n):
    if ll[tmp][i] == 1 and seen[i] == 0:
      seen[i] = 1
      dfs(i)

n,m = map(int,input().split())
ll =[[0]*n for _ in [0]*n]
edges = [list(map(int,input().split())) for _ in [0]*m]
for edge in edges:
  ll[edge[0]-1][edge[1]-1] = 1
  ll[edge[1]-1][edge[0]-1] = 1
originalll = ll.copy()
seen = [0]*n
ans = 0

for edge in edges:
  ll = copy.deepcopy(originalll)
  ll[edge[0]-1][edge[1]-1] = 0
  ll[edge[1]-1][edge[0]-1] = 0
  seen = [0]*n
  tmp = 0
  seen[tmp] = 1
  dfs(tmp)
  if sum(seen) < n:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def ABC075C_dfs(targ, root, graph, now):

    for dst in graph[now]:
        if targ == sorted([dst, now]):
            continue
        if dst not in root:
            root.append(dst)
            ABC075C_dfs(targ, root, graph, dst)


def ABC075C_Bridge():
    N, M = map(int, input().strip().split())
    graph = [[] for i in range(N)]

    if N > M:
        print(M)
        return 0
    
    edge = [[] for i in range(M)]
    for i in range(M):
        a1, b1 = map(int, input().strip().split())
        a1 -= 1
        b1 -= 1
        graph[a1].append(b1)
        graph[b1].append(a1)
        edge[i] = sorted([a1, b1])

    ans = 0
    for ed in edge:
        root = [0]
        ABC075C_dfs(ed, root, graph, 0)
        if len(root) != N:
            ans += 1

    print(ans)

def main():
    ABC075C_Bridge()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

    def find(self, x):
        if self.uf[x]<0: return x
        self.uf[x] = self.find(self.uf[x])
        return self.uf[x]

    def size(self, x):
        return -self.uf[self.find(x)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

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

ans = 0
for i in range(M):
    uf = UF(N)
    for j in range(M):
        if i==j: continue
        a, b = E[j]
        uf.union(a-1, b-1)
    if uf.n==2: ans+=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
l = [[] for _ in range(N)]
ab = []
ans = 0
for _ in range(M):
    ab.append([int(i)-1 for i in input().split()])
    l[ab[-1][0]].append(ab[-1][1])
    l[ab[-1][1]].append(ab[-1][0])
for a, b in ab:
    stack = []
    seen = [False]*N
    stack.append(0)
    seen[0] = True
    while len(stack) != 0:
        v = stack.pop()
        for v2 in l[v]:
            if v == a and v2 == b or v == b and v2 == a:
                continue
            if not seen[v2]:
                stack.append(v2)
                seen[v2] = True
    if False in seen:
        ans += 1

print(ans)

Submission status: Accepted

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)  # この変数xに格納されているものは必ず根のノード
        y = self.find(y)  # この変数yに格納されているものは必ず根のノード
        if x == y:
            return  # もし同じ親ならば何も起こらない

        if self.parents[x] > self.parents[y]:  # それぞれ、要素の個数が負で格納されている
            # yのグループの方が要素が多いの場合（yの方が値が小さいということは、負の世界では値が大きいため）
            x, y = y, x  # 必ずxの方が要素が多い状態にする

        self.parents[x] += self.parents[y]  # 負の値だが、これでいい
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    def size(self, x):
        return -self.parents[self.find(x)]  # 親まで辿ればグループの大きさが負で格納されているため、それにマイナスをつけてreturnする

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 親が同じならTrueが返却される

    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_counts(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 = map(int, input().split())  # N頂点, M辺の無向連結グラフ

edges = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    edges.append((a, b))
ans = M # 全ての辺が橋だと仮定する
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uf.union(edges[j][0], edges[j][1])
    if min(uf.parents) == -N:  # その辺がなくても全てのノードが繋がるならばその辺は橋ではない
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
e=[[] for i in range(N)]
tester=[None]*M
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  e[a].append(b)
  e[b].append(a)
  tester[i]=set([a,b])
  
ans=0
for test in tester:
  stack=[]
  stack.append([0,-1])
  seen=[0 for i in range(N)]
  while stack:
    node=stack.pop()
    v=node[0]
    parent=node[1]
    if seen[v]==1:
      continue
    seen[v]=1
    childs=e[v]
    for child in childs:
      if child==parent:
        continue
      if test==set([v,child]):
        continue
      stack.append([child,v])
      
  if sum(seen)!=N:
    ans+=1
print(ans)

Submission status: Accepted

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

not_bridge = 0
def dfs(node, finished):
    finished.add(node)
    global not_bridge
    if len(finished) == n:
        not_bridge += 1
    else:
        for i in adjacent_list[node]:
            if i not in finished:
                dfs(i, finished)
    
#iが省く要素
for i in range(m):
    adjacent_list = [[]for i in range(n+1)]
    finished = set()
    for j in range(m):
        if i != j:
            a, b = data[j]
            adjacent_list[a].append(b)
            adjacent_list[b].append(a)
    dfs(1, finished)
print(m - not_bridge)

Submission status: Accepted

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

n, m = map(int, input().split())
l = [[] for _ in range(n)]
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  ab.append((a, b))
seen = [False]*n
def dfs(v):
  for i in l[v]:
    if not seen[i]:
      seen[i] = True
      dfs(i)
ans = 0
for a, b in ab:
  l[a-1].remove(b-1)
  l[b-1].remove(a-1)
  c = 0
  for i in range(n):
    if not seen[i]:
      dfs(i)
      c += 1
  if c > 1:
    ans += 1
  seen = [False]*n
  l[a-1].append(b-1)
  l[b-1].append(a-1)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
l=[[] for i in range(N)]
e = [[int(i) for i in input().split()] for i in range(M)]
e0=e
c=0

def DFS(v):
  seen.append(v)
  for v2 in l[v]:
    if not v2 in seen:
      DFS(v2)
  return seen

for i in range(M):
  seen=[]
  l=[[] for i in range(N)]
  for j in range(M):
    if j!=i:
      l[(e[j][0])-1].append(e[j][1]-1)
      l[(e[j][1])-1].append(e[j][0]-1)
  S=DFS(0)
  if len(S)!=N:c+=1
print (c)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    edges = []
    s = -1
    for i in range(M):
        a, b = (int(i)-1 for i in input().split())
        if i == 0:
            s = a
        G[a].append(b)
        G[b].append(a)
        edges.append((a, b))

    def dfs(v, seen, remove_edge):
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                if (u, next_v) == remove_edge or (next_v, u) == remove_edge:
                    continue
                seen[next_v] = True
                todo.append(next_v)
                break
            else:
                todo.pop()

    ans = 0
    for e in edges:
        seen = [False] * N
        dfs(s, seen, e)
        if all(seen):
            continue
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N,M=map(int,input().split())
G = [[] for i in range(N)]
A = []
B = []

for i in range(M):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
    A.append(a)
    B.append(b)


def dfs(x):
    global old
    old[x] = True
    for i in G[x]:
        if not(old[i]):
            dfs(i)

ans = 0
for i in range(M):
    a,b = A[i], B[i]
    G[a].remove(b)
    G[b].remove(a)

    old = [False]*N
    dfs(0)
    if old != [True]*N:
        ans += 1

    G[a].append(b)
    G[b].append(a)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100)

N, M = map(int,input().split())
admat = [[0] * N for _ in range(N)]
edges = []
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    admat[a][b] = 1
    admat[b][a] = 1
    edges.append((a, b))

def dfs(v):
    visited[v] = 1
    for nv, bit in enumerate(admat[v]):
        if bit == 0:
            continue
        if not visited[nv]:
            dfs(nv)

ans = 0

for a, b in edges:
    visited = [0] * N
    admat[a][b] = 0
    admat[b][a] = 0
    dfs(0)
    if all(visited):
        pass
    else:
        ans += 1
    admat[a][b] = 1
    admat[b][a] = 1

print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def main():
    N,M=MI()
    AB=LLIN_(M)
    matrix = [[0]*N for _ in range(N)]

    def dfs(matrix):
        stack = [0]
        visited = set([0])
        while stack:
            u = stack.pop()
            for i,v in enumerate(matrix[u]):
                if v and i not in visited:
                    stack.append(i)
                    visited.add(i)
        return len(visited)!=len(matrix) #非連結になった
    
    for i,(a,b) in enumerate(AB):
        matrix[a][b] = 1
        matrix[b][a] = 1
    ans = 0
    for i,(a,b) in enumerate(AB):
        matrix[a][b] = 0
        matrix[b][a] = 0
        ans += dfs(matrix)
        matrix[a][b] = 1
        matrix[b][a] = 1
    print(ans)
if __name__ == '__main__':
    main()