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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    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.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)


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

ans = 0
for i in range(M):
    A, B = ways[i]
    tree = UnionFind(N)
    for j in range(M):
        if i != j:
            a, b = ways[j]
            tree.unite(a, b)
    if not tree.same(A, B):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def bridge(G, N):
    result = set()
    label = [None] * (N+1)
    gen = 0
    cost = [0] * (N+1)
    def dfs(u, p):
        nonlocal gen
        res = 0
        for v in G[u]:
            if v == p:
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                r = dfs(v, u)
                if r == 0:
                    result.add((u, v) if u < v else (v, u))
                res += r
        res -= cost[u]
        return res
    for v in range(N):
        if not label[v]:
            label[v] = gen; gen += 1
            r = dfs(v, -1)
            assert r == 0, r
    return result

from collections import deque

N,M,*abf = map(int, open(0).read().split())
ab = [abf[i*2:i*2+2] for i in range(M)]
connected = [[] for _ in range(N+1)]
ans = 0
for a, b in ab:
    connected[a].append(b)
    connected[b].append(a)
print(len(bridge(connected,N)))

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7


N,M = I()
links = [[] for _ in range(N)]
link = []
for i in range(M):
    a,b = I()
    links[a-1].append(b-1)
    links[b-1].append(a-1)
    link.append((a-1,b-1))
def dfs(n):
    if visited[n] == 1:
        return
    visited[n] = 1
    L = linky[n]
    for l in L:
        dfs(l)
ans = 0
for i in range(M):
    visited = [0]*N
    linky = deepcopy(links)
    a,b = link[i]
    linky[a].remove(b)
    linky[b].remove(a)
    dfs(0)
    if 0 in visited:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict,deque
    N,M = map(int,input().split())
    AB = []
    for _ in range(M):
        a,b = map(int,input().split())
        AB.append((a-1,b-1))
    ans = M
    for i in range(M):
        s,g = AB[i]

        edge = defaultdict(list)
        for j in range(M):
            if i == j:
                continue
            a,b = AB[j]
            edge[a].append(b)
            edge[b].append(a)

        visited = [False]*N
        targets = deque([s])
        while targets:
            t = targets.popleft()
            visited[t] = True
            for dest in edge[t]:
                if visited[dest]:
                    continue
                if dest == g:
                    ans -= 1
                    break
                targets.append(dest)
            else:
                continue
            break
    print(ans)
        
        







main()

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())
ms = [list(map(int, input().split())) for _ in range(m)]
res = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i!=j:
            uf.union(ms[j][0]-1,ms[j][1]-1)
    if len(uf.roots())!=1:
        res += 1
print(res)

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

## begin library unionfind
## usage: uf = UnionFind()
## usage: r = uf.Find_Root(x)
## usage: uf.Unite(x, y)
## usage: bool = uf.isSameGroup(x, y)
## usage: n = uf.Count(x)
class UnionFind():

    def __init__(self, n):
        self.n = n # number of nodes
        # if root[x]<0 then x is root and it has |x| leafs
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # find root of node x
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # path compression
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # unite two trees which has node x and node y
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # same tree
        if(x == y):
            return
        # different tree
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # if same rank (same depth)
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # return number of leafs
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

## end library unionfind

N, M = iInM()
AB = iInLD1(M)

## 枝を一つずつ選んで、それ以外を全部つなげてみて、非連結になるか見る
## 一つの森を作る計算量: MlogN
## それをM回繰り返すので、全体の計算量: M^2 logN = N^4 logN

ans = 0
for i in range(M):
    ## 選んだ枝以外で森を作る
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uf.Unite(AB[j][0], AB[j][1])
    if uf.Count(0) != N:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque
n,m = map(int,input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
joint = [[]for _ in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
    joint[a[i]].append(b[i])
    joint[b[i]].append(a[i])

ans = 0
jointdef = copy.deepcopy(joint)
for i in range(m):
    joint = copy.deepcopy(jointdef)
    joint[a[i]].remove(b[i])
    joint[b[i]].remove(a[i])
    
    looked = [1 for _ in range(n)]
    looked[0] = 0
    queue = deque([0])
    while(queue):
        now = queue.popleft()
        for i in joint[now]:
            if looked[i]:
                queue.append(i)
                looked[i] = 0
    if sum(looked) != 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 86
# ABC 075 C - Bridge

class UnionFindTree():
    def __init__(self, n):
        self.rank = [0] * n
        self.par = [x for x in range(n)]
        
    def find(self, x):
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            self.rank[x] += 1
    
    def same(self, x, y):
        return (self.find(x) == self.find(y))

n, m = map(int, input().split())
ab_l = [[int(x)-1 for x in input().split()] for y in range(m)]

ans = 0

for i in range(m):
    UF = UnionFindTree(n)
    for j in range(m):
        if i != j:
            UF.unite(ab_l[j][0], ab_l[j][1])
    for j in range(1,n):
        if not UF.same(0, j):
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
def Graph(ab):
    G = [[] for i in range(n)]
    for a, b in ab:
        G[a - 1].append(b)
        G[b - 1].append(a)
    return G

from collections import deque
def dfs(pair):
    q = deque()
    q.append((1, -1, 0))
    log = [0] * n
    log[0] = 1
    while q:
        V, P, S = q.popleft()
        if S == 0:
        #下に遷移していく処理
        #q.append((V, P, 1))
            for new_v in G[V - 1]:
                if new_v == P:continue
                if set(pair) == {V, new_v}:continue 
                if log[new_v - 1]:continue 
                log[new_v - 1] = 1
                q.append((new_v, V, 0))
    return sum(log) == n 


n, m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
G = Graph(ab)

res = 0
for t in ab:
    if dfs(t):
        #print(t)
        continue
    res += 1
print(res)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [1]*n
    
    def root(self, x):
        if x == self.p[x]:
            return x
        self.p[x] = y = self.root(self.p[x])
        return y
    
    def unite(self, x, y):
        px = self.root(x); py = self.root(y)
        if px == py:
            return 0
        rx = self.rank[px]; ry = self.rank[py]
        if ry < rx:
            self.p[py] = px
        elif rx < ry:
            self.p[px] = py
        else:
            self.p[py] = px
            self.rank[px] += 1
        return 1

    def same(self, x, y):
        px = self.root(x); py = self.root(y)
        return px == py

N,M = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(M)]
count = 0
for i in range(M):
    a,b = AB[i]
    union_find = UnionFind(N+10)
    for j in range(M):
        if i == j:
            continue
        union_find.unite(AB[j][0],AB[j][1])
    if not union_find.same(a,b):
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, remove):
        for u in tree[v]:
            if [u, v] == remove or [v, u] == remove:
                continue
            elif visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u, remove)

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

    res = 0
    for remove in edge:
        visited = [False for _ in range(n)]
        visited[0] = True
        dfs(0, remove)
        if not all(visited):
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append([b,i])
    V[b].append([a,i])
ans = 0
for i in range(m):
    q = deque([])
    reach = [0] + [-1]*n
    q.append(1)
    reach[1] = 0
    while q:
        x = q.popleft()
        for X,j in V[x]:
            if j == i:
                pass
            else:
                if reach[X] == -1:
                    q.append(X)
                    reach[X] = 0
    if -1 in reach:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        if f!=a or t!=b: dfs(t)

n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]
V = [[] for _ in range(n)]
for a, b in E: V[a].append(b); V[b].append(a)
ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a)
    if vis[b] == 0: ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(a, b, f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        if f!=a or t!=b: dfs(a, b, t)

n, m = map(int, input().split())
E, V = [], [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    E.append([a, b])
    V[a].append(b); V[b].append(a)
ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a, b, a)
    if vis[b] == 0: ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(a, b, f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        if f!=a or t!=b: dfs(a, b, t)

n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]
V = [[] for _ in range(n)]
for a, b in E: V[a].append(b); V[b].append(a)
ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a, b, a)
    if vis[b] == 0: ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

V = [[] for _ in range(n)]
for a, b in E:
    V[a].append(b)
    V[b].append(a)

def dfs(a, b, f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        if f==a and t == b: continue
        dfs(a, b, t)

ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a, b, a)
    if vis[b] == 0: ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]
V = [[] for _ in range(n)]
for a,b in E:
    V[a].append(b)
    V[b].append(a)

def dfs(a,b,f,i):
    # if i>=n:
    #     return
    if vis[f] == 1: return
    vis[f] = 1
    # print('f',f)
    for t in V[f]:
        if f==a and t == b: continue
        # if t == b: continue
        if vis[t] == 1: continue
        # print(t)
        dfs(a,b,t,i+1)

ans = 0
for a, b in E:
    vis = [0]*n
    dfs(a,b,a,1)
    # print(a,b,vis)
    if vis[b] == 0:
        ans += 1
    # print('----')

# print(E)
# print(V)

print(ans)

Submission status: Accepted

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

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

def bridge(G, N):
    result = set()
    label = [None] * N
    gen = 0
    cost = [0] * N
    
    def dfs(u, p):
        nonlocal gen
        res = 0
        for v in G[u]:
            if v == p:
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen
                gen += 1
                r = dfs(v, u)
                if r == 0:
                    result.add((u, v) if u < v else (v, u))
                res += r
        res -= cost[u]
        return res

    for v in range(N):
        if not label[v]:
            label[v] = gen
            gen += 1
            r = dfs(v, -1)
            assert r == 0, r
    return result

res = bridge(G, N)
print(len(res))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for i in range(M):
    d = defaultdict(list)
    for j in range(M):
        if j==i:continue
        a, b = l[j]
        d[a].append(b)
        d[b].append(a)
    q = [a]
    used = [False]*(N+1)
    used[0] = True
    used[a] = True
    while q:
        s = q.pop()
        for t in d[s]:
            if used[t]:continue
            used[t] = True
            q.append(t)
    if all(used):
        ans -= 1
print(ans)

Submission status: Accepted

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

#union-find
#初期化 par:親の番号
#par = [i for i in range(n)]
#木の根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x] 
#xとyが同じ集合に属するか否か
def same(x, y):
    return root(x) == root(y)
#xとyの属する集合を併合
def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    par[x] = root(y)

cnt = 0
for i in range(m):
    par = [k for k in range(n+1)]
    for j in range(m):
        if i == j:
            continue
        unite(a[j], b[j])
    if not same(a[i], b[i]):
        cnt += 1
print(cnt)

Submission status: Accepted

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

#Union-Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]


ans=0
for i in range(m):
    #初期化
    par = [-1]*n
    for j in range(m):
        if j==i:
            continue
        else:
            unite(side[j][0],side[j][1])
    if not same(side[i][0],side[i][1]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from copy import deepcopy
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


class UnionFind():
    def __init__(self, n):
        self.n = n
        # 各要素の親要素 親は -(その集合の要素数)
        self.parents = [-1] * n

    def find(self, x):
        '''要素 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 が属する集合と要素 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):
        '''要素 x が属する集合の要素数を返す'''
        return -self.parents[self.find(x)]

    def same(self, x, y):
        '''要素 x と要素 y が同じ集合に属するかを返す'''
        return self.find(x) == self.find(y)

    def members(self, x):
        '''要素 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 = LI()
    edges = [LI() for _ in range(m)]
    ans = 0
    for remove_u, remove_v in edges:
        uf = UnionFind(n)
        for u, v in edges:
            if u == remove_u and v == remove_v:
                continue
            u, v = u - 1, v - 1
            uf.union(u, v)
        if len(uf.roots()) > 1:
            ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from copy import deepcopy
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


def dfs(graph, v, visited):
    visited.add(v)
    for nv in graph[v]:
        if nv not in visited:
            dfs(graph, nv, visited)
    return visited


def is_connected(graph, nodes_cnt):
    visited = dfs(graph, 1, set())
    # 頂点1から一気に全頂点に訪問できているか
    if len(visited) == nodes_cnt:
        return True
    else:
        return False


n, m = LI()
edges = [LI() for _ in range(m)]
g = defaultdict(set)
for u, v in edges:
    g[u].add(v)
    g[v].add(u)

ans = 0
# 辺を一本ずつ除いていく
for u, v in edges:
    H = deepcopy(g)
    H[u] -= {v}
    H[v] -= {u}
    if not is_connected(H, n):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from copy import deepcopy


def dfs(graph, v, visited):
    visited.add(v)
    for nv in graph[v]:
        if nv not in visited:
            dfs(graph, nv, visited)
    return visited


def is_connected(graph, nodes_cnt):
    visited = dfs(graph, 1, set())
    if len(visited) == nodes_cnt:
        return True
    else:
        return False


N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
G = defaultdict(set)
for u, v in edges:
    G[u].add(v)
    G[v].add(u)
ans = 0
for u, v in edges:
    H = deepcopy(G)
    H[u] -= {v}
    H[v] -= {u}
    if not is_connected(H, N):
        ans += 1
print(ans)

Submission status: Accepted

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


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def find(n):
    if root[n] == n:
        return n
    else:
        parent = root[n]
        root[n] = find(parent)
        return root[n]

def unite(x,y):
    rx = find(x)
    ry = find(y)
    if rx == ry:
        return
    else:
        root[rx] = ry

def same(x,y):
    if find(x) == find(y):
        return True
    else:
        return False

def member(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

def member_count(x):
    return len(member(x))

n , m = map(int,input().split())
route = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(m)]
ans = 0
for i in range(m):
    root = [k for k in range(n)]
    for j in range(m):
        if i == j:
            continue
        a,b = route[j]
        unite(a,b)
    if member_count(0) != n:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        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
    #sizeの大きいほうがx
    if par[x] > par[y]: x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

n, m = map(int, input().split())
ab = []
ans = m
for _ in range(m):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])
for i in range(m):
    par = [-1]*n
    for j in range(m):
        if i==j: continue
        unite(ab[j][0], ab[j][1])
    if -min(par) == n: ans -= 1
print(ans)

Submission status: Accepted

Solution code:
# ABC075C

import sys
input=sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.p=[-1]*n
        
    def root(self, x):
        st=[]
        while(self.p[x]>=0):
            st.append(x)
            x=self.p[x]
        for y in st:
            self.p[y]=x
        return x
    def find(self, x, y):
        return self.root(x)==self.root(y)
    def union(self, x, y):
        r1=self.root(x)
        r2=self.root(y)
        if r1==r2:
            return
        up=self.p
        p1=up[r1]
        p2=up[r2]
        if p1<=p2:
            up[r2]=r1
            if p1==p2:
                up[r1]-=1
        else:
            up[r1]=r2
            
def main():
    N,M=map(int,input().split())
    AB=[tuple(map(lambda x: int(x)-1,input().split())) for i in range(M)]
    
    ans=0
    for i in range(M):
        uft=UnionFind(N)
        for j in range(M):
            if i!=j:
                uft.union(AB[j][0],AB[j][1])
        ps=0
        for x in range(N):
            if uft.p[x]<0:
                ps+=1
        if ps!=1:
            ans+=1
    print(ans)
        
    
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list()
for i in range(m):
    l.append(list(map(int,input().split())))
p=0
for o in range(m):
    d={i:[] for i in range(1,n+1)}
    for i in range(m):
        if i==o:
            continue
        a,b=l[i]
        d[a].append(b)
        d[b].append(a)
    q=[1]
    s={i:1 for i in range(1,n+1)}
    while len(q)>0:
        for i in d[q.pop()]:
            if s[i]:
                s[i]=0
                q.append(i)
    #print(s)
    if 1 in s.values():
        p+=1
print(p)

Submission status: Accepted

Solution code:
##### UnionFind #####
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), *q = [list(map(int, o.split())) for o in open(0)]
c = 0
for i in range(m):
    UF = UnionFind(n)
    for j, (a, b) in enumerate(q):
        if i == j:continue
        UF.union(a - 1, b - 1)
    if UF.group_count() > 1:
        c += 1
print(c)