Problem:


Score : 300 points

Problem Statement

You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges.

The i-th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i.  

An edge whose removal disconnects the graph is called a bridge.

Find the number of the edges that are bridges among the M edges.  

Notes

A self-loop is an edge i such that a_i=b_i (1 \leq i \leq M).

Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j (1 \leq i<j \leq M).

An undirected graph is said to be connected when there exists a path between every pair of vertices.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq min(N(N−1)⁄2,50)

1 \leq a_i<b_i \leq N

The given graph does not contain self-loops and double edges.

The given graph is connected.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

Output

Print the number of the edges that are bridges among the M edges.

Sample Input 1

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

Sample Output 1

4

The figure below shows the given graph:

The edges shown in red are bridges. There are four of them.

Sample Input 2

3 3
1 2
1 3
2 3

Sample Output 2

0

It is possible that there is no bridge.

Sample Input 3

6 5
1 2
2 3
3 4
4 5
5 6

Sample Output 3

5

It is possible that every edge is a bridge.



Sample input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7


Sample output:
4

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

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


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

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    val1, val2 = map(int, input().split())
    val1 -= 1
    val2 -= 1
    a[i], b[i] = val1, val2
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        else:
            uf.unite(a[j], b[j])
    cnt = uf.find(0)
    #print(uf.d)
    for j in range(n):
        if uf.find(j) != cnt:
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
# 各頂点を結ぶクエリー(a, bの情報)ごとに、
# それを実行しなくてもたどり着ける頂点が総頂点数(n)に一致するかを判定する。
n, m = map(int, input().split())

queries = []
for _ in range(m):
    a, b = map(int, input().split())
    queries.append((a, b))

def dfs(graph, n):
    visited = [False] * (n + 1)
    visited[0] = True # 1-indexedなので、0番目は関係ない
    stack = [1]
    num = 0
    while stack:
        t = stack.pop()
        for node in graph[t]:
            if visited[node]:
                continue
            visited[node] = True
            stack.append(node)
            num += 1
    if num == n:
        return True
    return False

ans = 0
for i in range(m):
    graph = [[] for _ in range(n + 1)]
    for j in range(m):
        if i == j:
            continue
        a, b = queries[j]
        graph[a].append(b)
        graph[b].append(a)
    if not dfs(graph, n):
        ans += 1
print(ans)

Submission status: Accepted

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

brides = []
for _ in range(m):
    a, b = map(int, input().split())
    brides.append((a, b))


class Union:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.rank = 0

    def get_root(self):
        n = self
        while n.parent != n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val

ans = 0
for i in range(m):
    unions = []
    for val in range(n):
        unions.append(Union(val))
    for index, (a, b) in enumerate(brides):
        if i == index:
            continue
        x, y = unions[a - 1], unions[b - 1]
        x_root = x.get_root()
        y_root = y.get_root()
        if x_root.rank == y_root.rank:
            x_root.rank += 1
            y_root.parent = x_root
        elif x_root.rank > y_root.rank:
            y_root.parent = x_root
        else:
            x_root.parent = y_root

    groups = [None] * n
    for j, u in enumerate(unions):
        root = u.find_set()
        groups[j] = root
    for g in range(1, n):
        if groups[g - 1] != groups[g]:
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
import copy
N,M=[int(s) for s in input().split()]
TO=[set() for _ in range(N)]
Edges=[[int(s) for s in input().split()] for _ in range(M)]
for [a,b] in Edges:
  TO[a-1].add(b-1)
  TO[b-1].add(a-1)
ans=0
for [a,b] in Edges:
  to=copy.deepcopy(TO)
  to[a-1].remove(b-1)
  reach={a-1}
  while(reach):
    k=reach.pop()
    if k==b-1:
      break
    while(to[k]):
      m=to[k].pop()
      reach.add(m)
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        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 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
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
uf = UnionFind(N)
l = []
count=0
for i in range(M):
    a, b = map(int,input().split())
    l.append([a, b])
    
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i != j:
            uf.union(l[j][0], l[j][1])
    if not uf.same_check(l[i][0],l[i][1]):
        count+=1
print(count)

Submission status: Accepted

Solution code:
# I used the below code as a reference.
# https://atcoder.jp/contests/abc075/submissions/10369947
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

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

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

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

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

    def roots(self):
        return [i for i in self._root if i < 0]

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

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
            uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

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

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

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

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

    def roots(self):
        return [i for i in self._root if i < 0]


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

nodes = []
for _ in range(m):
    a, b = map(int, input().split())
    nodes.append((a, b))

cnt = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j:
          uf.unite(nodes[j][0]-1, nodes[j][1]-1)
    cnt += (len(uf.roots()) != 1)
print(cnt)

Submission status: Accepted

Solution code:
import sys

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:
'''
https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
深さ優先探索でも解ける
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        #要素xの根を返す, その過程で経路圧縮も行う
        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
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x #根をくっつける(片方を親にする)
    
        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]
    
        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        #xが属するグループの要素全てを返す
        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 all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        #print(uf)
        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)]
    res = 0
    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if i==j:
                continue
            a,b = edge[j]
            uf.union(a-1,b-1)
        if uf.size(0)!=n:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
深さ優先探索でも解ける
'''
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    class UnionFind():
        #n個の要素を番号0~n-1で管理する
        #parents:要素の親(1つ上), 要素が根の場合サイズを表す
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        #要素xの根を返す, その過程で経路圧縮も行う
        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
            #それぞれのsizeで比べる
            if self.parents[x] > self.parents[y]:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x #根をくっつける(片方を親にする)
    
        #xが属するグループのsize
        def size(self, x):
            return -self.parents[self.find(x)]
    
        #xとyが同じグループかどうか
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        #xが属するグループの要素全てを返す
        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 all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        #print(uf)
        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)]
    res = 0
    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if i==j:
                continue
            a,b = edge[j]
            uf.union(a-1,b-1)
        if uf.size(0)!=n:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
node=[[0 for _ in range(n)] for _ in range(n)]
aL=[0 for _ in range(m)]
bL=[0 for _ in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    node[a-1][b-1]=1
    node[b-1][a-1]=1
    aL[i]=a
    bL[i]=b
    
tmp1=copy.deepcopy(node)
chk=[0 for _ in range(n)]
def DFS(x):
    chk[x]=1
    for i in range(n):
        if chk[i]!=1 and tmp1[x][i]==1:
            tmp1[x][i]=0
            tmp1[i][x]=0
            chk[i]=1
            DFS(i)
    return chk

cnt=0
for j in range(m):
    tmp1[aL[j]-1][bL[j]-1]=0
    tmp1[bL[j]-1][aL[j]-1]=0
    if sum(DFS(0))!=n:
        cnt+=1
    tmp1=copy.deepcopy(node)
    chk=[0 for _ in range(n)]
print(cnt)

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())
ab = [list(map(int, input().split())) for _ in range(M)]

s = 0

for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j != i:
            uf.union(ab[j][0] - 1, ab[j][1] - 1)
    s += (len(uf.roots()) != 1)

print(s)

Submission status: Accepted

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

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 int_(num_str):
    return int(num_str) - 1

N, M = map(int, input().split())
ablist = [tuple(map(int_, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, ab in enumerate(ablist):
        if i == j:
            continue
        uf.union(*ab)
    if uf.group_count() > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# なぜかunion findが動かないので手癖で復習
n, m = map(int, input().split())
# par = [i for i in range(n)]

def root(x, par):
    if x == par[x]:
        return x
    else:
        t = root(par[x], par)
        par[x] = t
        return t

def same(a, b, par):
    return root(a, par) == root(b, par)

def union(a, b, par):
    if not same(a, b, par):
        ra = root(a, par)
        rb = root(b, par)
        # par[rb] = ra
        par[rb] = a

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

ans = 0
for i in range(m):
    par = [k for k in range(n)]
    for j in range(m):
        if i == j:
            continue
        a, b = edges[j]
        if same(a, b, par):
            continue
        union(a, b, par)
    # 以降が.....
    a, b = edges[i]
    if not same(a, b, par):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from scipy.sparse.csgraph import floyd_warshall

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

cnt=0
for i in range(m):
  ll=deepcopy(l)
  del ll[i]

  d=[[float('inf')]*n for i in range(n)]
  for i in range(n):
    d[i][i]=0

  for a,b in ll:
    a-=1
    b-=1
    d[a][b]=1
    d[b][a]=1

  s=floyd_warshall(d)
  for i in s:
    if float('inf') in i:
      cnt+=1
      break

print(cnt)

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

cnt=0
for i in range(m):
  ll=deepcopy(l)
  del ll[i]

  tree=[[] for i in range(n)]
  for a,b in ll:
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)

    dist=[-1 for i in range(n)]

    s=ll[0][0]-1
    dist[s]=0
    dq=deque()
    dq.append(s)

    while dq:
      x=dq.popleft()
      for i in tree[x]:
        if dist[i]==-1:
          dq.append(i)
          dist[i]=dist[x]+1

  if -1 in dist:
    cnt+=1
print(cnt)

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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

from copy import deepcopy

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

cnt=0
for i in range(m):
  uf=UnionFind(n)
  ll=deepcopy(l)
  del ll[i]
  for a,b in ll:
    a-=1
    b-=1
    uf.union(a,b)
  if uf.group_count()>=2:
    cnt+=1
print(cnt)

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())
ablist = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for index, ab in enumerate(ablist):
        a, b = ab
        if index != i:
            uf.union(a-1, b-1)
    if uf.group_count() >= 2:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
GRAPH = [[0]*n for _ in range(n)]
EDGES = []

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    GRAPH[a][b] = GRAPH[b][a] = 1
    EDGES.append((a, b))


def make_dfs():
    visited = [0]*n

    def inner(v):
        visited[v] = 1
        for v2 in range(n):
            if not GRAPH[v][v2]:
                continue
            if visited[v2]:
                continue
            inner(v2)
        return visited
    return inner


ans = 0
for a, b in EDGES:
    GRAPH[a][b] = GRAPH[b][a] = 0
    dfs = make_dfs()
    if sum(dfs(0)) != n:
        ans += 1
    GRAPH[a][b] = GRAPH[b][a] = 1

print(ans)

Submission status: Accepted

Solution code:
def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


def roots():
    roots = []
    for i in range(N):
        roots.append(find_root(i))
    return roots


def group_count():
    return len(set(roots()))


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

parent = [i for i in range(N)]  # 根
rank = [1] * N  # 深さ
size = [1] * N  # iを根とするグループのサイズ

edge = [[ab[M - 1 - i][0] - 1, ab[M - 1 - i][1] - 1] for i in range(M)]

for i in range(M):
    unite(edge[i][0], edge[i][1])
count = group_count()

ans = 0
for j in range(M):
    # 再構築するため、初期化し直す
    parent = [i for i in range(N)]
    rank = [1] * N
    size = [1] * N
    for i in range(M):
        if j == i:
            continue
        unite(edge[i][0], edge[i][1])
    if group_count() > count:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines

# 0-indexed
class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return x
  
  def same(self,x,y):
    return self.root(x)==self.root(y)
  
  def unite(self,x,y):
    x=self.root(x)
    y=self.root(y)
    if x==y:
      return
    if self.size[x]>self.size[y]:
      # 大きい方にくっつける
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
N,M=map(int,readline().split())
edges=[None]*M
for i in range(M):
  a,b=map(int,readline().split())
  edges[i]=[a-1,b-1]

ans=0
# どの辺を使用しないかのループ
for i in range(M):
  # 辺iを使用しない場合
  UF=UnionFind(N)
  for m in range(M):
    if m==i:
      continue
    UF.unite(edges[m][0],edges[m][1])
  # 連結であれば0が属するグラフのサイズはNである
  if UF.get_group_size(0)!=N:
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
#075_C
n,m=map(int,input().split())
ans=0

edges=[]
graph=[[False for _ in range(n)] for _ in range(n)]

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

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

for x in edges:
    a,b=x
    graph[a][b]=False
    graph[b][a]=False
    visit=[False for _ in range(n)]
    
    dfs(0)
    ans+=any([visit[i]==False for i in range(n)])
    
    graph[a][b]=True
    graph[b][a]=True
    
print(ans)

Submission status: Accepted

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

E = [[] for i in range(N)]

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

visited = []


def search(pos):
    for n_pos in E[pos]:
        if n_pos not in visited:
            visited.append(n_pos)
            search(n_pos)

count = 0
for i in range(M):
    visited = []
    E = [[] for i in range(N)]
    for j in range(M):
        if j == i:
            continue
        E[ab[j][0]].append(ab[j][1])
        E[ab[j][1]].append(ab[j][0])
    search(0)
    if len(visited) < N:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ab=[]
for i in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    ab.append([A,B])
res=0

for i in range(M):
    par=[j for j in range(N)]
    siz=[1 for _ in range(N)]
    rank=[0 for _ in range(N)]
    for j in range(M):
        if(i==j):
            continue
        union(ab[j][0],ab[j][1])
    for i in range(1,N):
        if(not same(0,i)):
            res+=1
            break
print(res)

Submission status: Accepted

Solution code:
def dfs(v, matrix, visited):
    visited[v] = True
    for i in range(n):
        if visited[i]:
            continue
        if not matrix[v][i]:
            continue
        dfs(i, matrix, visited)


n, m = map(int, input().split())
ab = [tuple(map(lambda x: (int(x) - 1), input().split())) for _ in range(m)]
matrix = [[False] * n for _ in range(n)]
for a, b in ab:
    matrix[a][b] = True
    matrix[b][a] = True
visited = [False] * n
ans = 0

for a, b in ab:
    matrix[a][b] = False
    matrix[b][a] = False
    for i in range(n):
        visited[i] = False
    dfs(0, matrix, visited)
    if not all(visited):
        ans += 1
    matrix[a][b] = True
    matrix[b][a] = True
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    #要素数nで初期化
    #インスタンス変数の初期化
    def __init__(self, n):
        #root : 木の要素数
        #rnk : 木の高さ(rank)
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x]) 
            return self.root[x]
    
    """木の合併"""
    def Union(self, x, y):
        #入力ノードの親を探索
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        #既に同じ木に所属する場合
        if (x==y):
            return 
        
        #異なる木に所属する場合 -> rnkから判断して合併する
        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
            
            #rnkが同じ(深さが同じ)場合
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


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

res = 0
for i in range(m):
    tmp_edge = edge[:i] + edge[i+1:]
    uf = UnionFind(n)
    for j in range(len(tmp_edge)):
        uf.Union(tmp_edge[j][0], tmp_edge[j][1])
    if not uf.isSameGroup(edge[i][0], edge[i][1]):
        res += 1
print(res)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par =[-1 for i in range(N)]
    def find(self,x):
        if self.par[x] < 0:
            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 x==y:
            return
        if self.par[x] > self.par[y]:
            x,y = y,x
        self.par[x] +=self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.find(x)]
    def same(self,x,y):
        return self.find(x)==self.find(y)

N,M=map(int,input().split(' '))
q = [list(map(int,input().split(' '))) for i in range(M)]
ans = 0
for i in range(M):
    tmp = q[:i]+q[i+1:]
    uf = UnionFind(N)
    for j,k in tmp:
        uf.unite(j-1,k-1)
    for l in range(N):
        if uf.size(l) != N:
            ans += 1
            break
print(ans)