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):
        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()}


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

edges = []

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

ans = 0
for ban in range(m):
    uf = UnionFind(n)
    for i in range(m):
        if ban == i:
            continue

        frm, to = edges[i]
        uf.union(frm, to)

    if len(uf.roots()) > 1:
        ans += 1

print(ans)

Submission status: Accepted

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

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.parents = [i for i in range(n)]
		self.rank = [1] * n
		self.size = [1] * n

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

	def union(self, x, y):
		x, y = self.find(x), self.find(y)
		if x == y: return
		if self.rank[x] < self.rank[y]:
			self.parents[x] = y
			self.size[y] += self.size[x]
		else:
			self.parents[y] = x
			self.size[x] += self.size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

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

cnt = 0
for i in range(m):
	uf = UnionFind(n)
	for j, e in enumerate(graph):
		if j == i: continue
		a, b = e[0], e[1]
		uf.union(a, b)
	a, b = graph[i][0], graph[i][1]
	if uf.group_size(0) < n: cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys


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


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.parent = [i for i in range(n_nodes)]
        self.rank = [1] * n_nodes
        self.size = [1] * n_nodes

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return 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[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    def get_n_groups(self):
        return len(self.get_parent_list())


def main():
    N, M = map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(M)]
    cnt = 0
    for i in range(M):
        Tree = UnionFind(N)
        for j in range(M):
            if i == j:
                continue
            else:
                Tree.unite(edge[j][0] - 1, edge[j][1] - 1)
        if Tree.get_n_groups() > 1:
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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


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


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes

        # self.parents[x] < 0 の時，xが根である．
        # また，xが根の時，(-1) * (同一グループの要素数) が格納されるようになる.
        self.parents = [-1] * n_nodes

    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

        # 常にxの方が要素数が多くなるように，スワップする
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        # 要素数の少ない方のグループを，要素数が多い方の木に貼る．
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def get_size(self, x):
        return -self.parents[self.find(x)]

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

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

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


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

    n_groups = base_tree.get_n_groups()
    ans = 0
    for i in range(M):
        tmp_tree = UnionFind(N)
        for j, (a, b) in enumerate(edges):
            if i == j:
                continue

            tmp_tree.union(a, b)

        tmp = tmp_tree.get_n_groups()
        if n_groups != tmp:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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


# main
N, M = map(int, sys.stdin.readline().strip().split())
edges = []
for _ in range(M):
	a, b = map(int, sys.stdin.readline().strip().split())
	edges.append((a-1, b-1))

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(edges):
        if i == j:
            continue
        uf.union(a, b)
    # print(uf.group_count())
    if uf.group_count() != 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
limit=50
graph=[[False]*limit for i in range(limit)]
visited=[]*limit

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

n,m=map(int,input().split())
a=[0]*m
b=[0]*m
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True
    
ans=0 
for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False
    visited=[False]*n
    dfs(0,n,graph,visited)
    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)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    adj = [list() for _ in range(N)]
    for a, b in edge:
        adj[a].append(b)
        adj[b].append(a)

    ans = 0
    for a, b in edge:
        visit = [False for _ in range(N)]
        que = queue.Queue()
        que.put(0)
        while not que.empty():
            c = que.get()
            visit[c] = True
            for n in adj[c]:
                if (c == a and n == b) or (c == b and n == a):
                    continue
                if not visit[n]:
                    que.put(n)
        if sum(visit) != N:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

par = [i for i in range(n)]
rank = [0]*n

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if rank[x]<rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

a = []
b = []

for i in range(m):
    x,y = map(int, input().split())
    a.append(x-1)
    b.append(y-1)

ans = 0
for i in range(m):
    par = [k for k in range(n)]
    rank = [0]*n
    # i番目の2頂点以外を連結
    for j in range(m):
        if i != j:
            unite(a[j],b[j])
            
    
    # 全ての点が連結してるか確認
    if not same(a[i],b[i]):
        ans+=1
  

print(ans)

Submission status: Accepted

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

d = [1]*N
def bfs(graph,s,d,n):
    for v in graph[s]:
        if d[v]:
            d[v] = 0
            bfs(graph,v,d,n)
    if d.count(0) != n:
        return 1
    else:
        return 0
ans = 0
for i in range(M):
    d = [1]*N
    graph1=copy.deepcopy(graph)
    graph1[edge[i][0]].remove(edge[i][1])
    graph1[edge[i][1]].remove(edge[i][0])
    ans+=bfs(graph1,0,d,N)

print(ans)

Submission status: Accepted

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

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

def adjacent(g, v):
    adj = []    
    for i in range(n):
        if g[v-1][i] == 1:
            adj.append(i+1)
    return adj


def dfs(g, v):
    visited = []
    stack = []
    
    stack.append(v)
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            for w in adjacent(g, node):
                if w not in visited:
                    stack.append(w)
    return visited
            

def cut(g):
    bridge = 0
    for i in range(n):
        for j in range(n):
            if g[i][j] == 1:
                g[i][j] = 0
                g[j][i] = 0
                if len(dfs(g,i+1)) < n:
                    bridge = bridge + 1
                g[i][j] = 1
                g[j][i] = 1
    bridge = bridge // 2
    return bridge

print(cut(graph))

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 resolve():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(M)]
    cnt = 0
    for i in range(len(AB)):
        uf = UnionFind(N)
        for edge in AB[:i]+AB[i+1:]:
            uf.union(edge[0]-1, edge[1]-1)
        if uf.find(AB[i][0]-1) != uf.find(AB[i][1]-1):
            cnt += 1
    print(cnt)


if '__main__' == __name__:
    resolve()

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 False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self,x,y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from itertools import combinations # (string,3) 3回
#from collections import deque
#import collections.defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    #Uni = UnionFind(n)
    # 最初に保存しておく
    bridge = []
    for i in range(m):
        s,e = map(lambda x: int(x) - 1,input().split())
        bridge.append((s,e))
    cnt = 0
    for i in range(m):
        # ある辺を取り除いた時
        Uni = UnionFind(n)
        for j,root in enumerate(bridge,start = 0):
            # もし、取り除いた辺とidxが一緒ならば、次にいく
            if i == j:
                continue
            s,t = root
            Uni.Union(s,t)
        # ここで構成完了
        s,t = bridge[i]
        if not Uni.same(s,t): # 頂点が一致しない # その経路は必要だった
            cnt += 1
    print(cnt)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N, M = (int(_) for _ in input().split())
    AB = [[int(_) for _ in input().split()] for __ in range(M)]
    edg = {}
    for ab in AB:
        a, b = ab
        if a in edg.keys():
            edg[a].append(b)
        else:
            edg[a] = [b]
        if b in edg.keys():
            edg[b].append(a)
        else:
            edg[b] = [a]

    def ikeru(i, j):
        visited = [False] * (N+1)
        d = deque()
        visited[i] = True
        for k in edg[i]:
            if k != j:
                d.append(k)
        while d:
            p = d.popleft()
            visited[p] = True
            for k in edg[p]:
                if not visited[k]:
                    d.append(k)
        return visited[j]

    ret = 0
    for i in range(M):
        a, b = AB[i]
        ret += not ikeru(a, b)
    print(ret)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
def resolve():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(M)]
    cnt = 0
    for i, edge in enumerate(AB):
        edges = AB[:i]+AB[i+1:]
        if not is_reachable(edges, edge[0], edge[1]):
            cnt += 1
    print(cnt)


def is_reachable(edges, src, dst):
    import collections
    stack = collections.deque()
    stack.append(src)

    while stack:
        pos = stack.pop()
        if pos == dst:
            return True
        _edges = []
        while edges:
            edge = edges.pop()
            if edge[0] == pos:
                stack.append(edge[1])
            elif edge[1] == pos:
                stack.append(edge[0])
            else:
                _edges.append(edge)
        edges = _edges
    return False


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

    #出力用
    def __str__(self):
        return "\n".join("{}: {}".format(r,self.members(r)) for r in self.roots())
        #"\n"はただの改行コード
        #str(辞書)を改行しながら表示する
        #print(インスタンス)で__str__に飛ぶ
        #出力過程で、membersで全要素にfindをしてる→逐一経路圧縮されてる！


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

ans=0
for i in range(m):
    uf=UnionFind(n)
    for j in range(m):
        if j==i:
            continue
        uf.union(*A[j])
    
    if len(uf.roots())!=1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def LowLink(Graph, N):
    def dfs(v, k, prev):
        used[v] = True
        order[v] = k
        low[v] = order[v]
        k += 1
        is_aps = False
        count = 0
        for w in Graph[v]:
            if not used[w]:
                count += 1
                k = dfs(w, k, v)
                low[v] = min(low[v], low[w])
                if prev != -1 and order[v] <= low[w]:
                    is_aps = True
                if order[v] < low[w]:
                    bridges.append([min(v, w), max(v, w)])
            elif w != prev:
                low[v] = min(low[v], order[w])
        if prev == -1 and count >= 2:
            is_aps = True
        if is_aps:
            aps.append(v)
        return k
    
    used = [False] * N
    order = [0] * N
    low = [0] * N
    aps = []
    bridges = []
    k = 0
    for i in range(N):
        if not used[i]:
            k = dfs(i, k, -1)
    aps.sort()
    bridges.sort()
    
    return aps, bridges


N, M = map(int,input().split())
G = [[] for _ 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)
aps, bridges = LowLink(G, N)
print(len(bridges))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

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

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


def main():
    n, m = list(map(int, readline().split()))
    edge = [list(map(int, readline().split())) for _ in range(m)]

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import string
import io

readline = sys.stdin.buffer.readline
n, m = map(int, readline().split())
es = []
for _ in range(m):
    a, b = map(int, readline().split())
    es.append((a, b))
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def same(x, y):
    return find(x) == find(y)
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
ans = 0
for i in range(m):
    par = [_ for _ in range(n + 1)]
    for j, k in enumerate(es):
        if i == j:
            continue
        a, b = k
        unite(a, b)
    a, b = es[i]
    if not same(a, b):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
paths=[]
cnt=0
for i in range(M):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1])
#print(tree)
for i in range(M):
    stop=paths[i]
    seen=[0]*N
    d=deque()
    d.append(0)
    while len(d)>0:
        v=d.popleft()
        seen[v]=1
        for j in tree[v]:
            if not(((v==stop[0])and(j==stop[1]))or((v==stop[1])and(j==stop[0])))and(seen[j]==0):
                d.append(j)
        #print(i,d,seen,stop)
        #input()
    if sum(seen)!=N:
        cnt=cnt+1
print(cnt)

Submission status: Accepted

Solution code:
def dfs(v):
    visited[v]=True
    for nv in range(n):
        if G[v][nv]==False:continue
        if visited[nv]:continue
        dfs(nv)

n,m=map(int,input().split())
G=[[False]*n for _ in range(n)]
ans=0
visited=[False for _ in range(n)]
A,B=[],[]
for i in range(m):
    a,b = map(int,input().split())
    A.append(b-1)
    B.append(a-1)
    G[a-1][b-1]=G[b-1][a-1]=True

for i in range(m):
    G[A[i]][B[i]]=G[B[i]][A[i]]=False
    visited = [False for _ in range(n)]
    dfs(0)
    if all(visited):
        ans += 1
    G[A[i]][B[i]]=G[B[i]][A[i]]=True

print(m-ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

## ダイクストラ

import heapq
def dijkstra_heap(s, edge):
    #始点sから各頂点への最短距離
    ###edge=[[e[0]:コスト, e[1]：目的地]...]
    #O(ElogV)
    d = [float("inf")] * N      #各頂点への最小距離を記憶
    used = [True] * N           #True:未確定
    d[s] = 0                    #スタート地点は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]]:
                if e[0]+d[v] > d[e[1]]:                     #既に求まってる最短距離以上なら枝刈り
                    continue
                heapq.heappush(edgelist, [e[0]+d[v], e[1]]) #最小値更新した頂点につながった頂点をプッシュ
    return d

N, M = mi()
memo = []
rel = [[] for i in range(N)]

for i in range(M):
    s, t = mi()
    s, t = s-1, t-1
    memo.append((s, t))
    rel[s].append([1, t])
    rel[t].append([1, s])

cnt = 0
for x in range(M):
    s, t = memo[x][0], memo[x][1]
    rel[s].remove([1, t])
    rel[t].remove([1, s])

    l = sorted(dijkstra_heap(0, rel))
    ind = bisect.bisect_left(l, float('inf'))
    if ind != N:
        cnt += 1

    rel[s].append([1, t])
    rel[t].append([1, s])

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

## DFS

from collections import deque
N, M = mi()
memo = []
rel = [[] for i in range(N)]

for i in range(M):
    s, t = mi()
    s, t = s-1, t-1
    memo.append((s, t))
    rel[s].append(t)
    rel[t].append(s)

cnt = 0
que = deque()
for x in range(M):
    s, t = memo[x][0], memo[x][1]
    rel[s].remove(t)
    rel[t].remove(s)

    que.append(0)
    used = [0]*N
    while que != deque():
        v = que.popleft()
        for nv in rel[v]:
            if not used[nv]:
                used[nv] = 1
                que.append(nv)
    if sum(used) != N:
        cnt += 1

    rel[s].append(t)
    rel[t].append(s)

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

## DFS

N, M = mi()
memo = []
rel = [[] for i in range(N)]

for i in range(M):
    s, t = mi()
    s, t = s-1, t-1
    memo.append((s, t))
    rel[s].append(t)
    rel[t].append(s)

def dfs(v):
    for nv in rel[v]:
        if not used[nv]:
            used[nv] = 1
            dfs(nv)
            if sum(used) == N:
                global flag
                flag = 1
                return

cnt = M
for x in range(M):
    s, t = memo[x][0], memo[x][1]
    rel[s].remove(t)
    rel[t].remove(s)
    flag = 0
    used = [0]*N
    dfs(0)
    if flag:
        cnt -= 1
    rel[s].append(t)
    rel[t].append(s)

print(cnt)