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.rank = [0] * n
        self.par = list(range(n))

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] >= self.rank[ry]:
            self.par[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        else:
            self.par[rx] = ry

    # find root
    def find(self, x):
        ch = []
        while self.par[x] != x:
            ch.append(x)
            x = self.par[x]
        for c in ch:
            self.par[c] = x
        return x

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

N, M = [int(x) for x in input().split()]
E = [[int(x) - 1 for x in input().split()] for _ in range(M)]

ans = 0
for (a, b) in E:
    uf = UnionFind(N)
    for (c, d) in E: # (a, b)以外の辺でunion findを作る
        if (c, d) != (a, b):
            uf.union(c, d)
    if not uf.same(a, b):
        ans += 1

print(ans)

Submission status: Accepted

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

all_use = (1 << N) - 1


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


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N, M = map(int, input().split())
graph = [[0]*N for _ in range(N)]
visited = [0]*N
ab = []
ans = 0

def dfs(u):
  visited[u] = 1
  for v in range(N):
    if graph[u][v] == 1 and visited[v] == 0:
      dfs(v)

for _ in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a][b] = 1
  graph[b][a] = 1
  ab += [[a, b]]

for _ in range(M):
  a, b = ab.pop(0)
  graph[a][b] = 0
  graph[b][a] = 0

  for i in range(N):
    visited[i] = 0
  
  dfs(0)
  
  if sum(visited) != N:
    ans += 1

  graph[a][b] = 1
  graph[b][a] = 1

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
ans = 0

def dijkstra(s, graph, n):
  dist = [float('inf')]*n
  dist[s] = 0
  num = [0]*n
  num[s] = 1
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        num[v] = num[u]
        heapq.heappush(q, [dist[v], v])
      elif dist[v] == dist[u] + weight:
        num[v] += num[u]
  return dist, num

for i in range(M):
  graph = [[] for _ in range(N)]
  for j in range(M):
    if i != j:
      a, b = ab[j]
      graph[a] += [[b, 1]]
      graph[b] += [[a, 1]]

  for j in range(N):
    d, _ = dijkstra(j, graph, N)
    if max(d) == float('inf'):
      ans += 1
      break
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque([0])
    c[0] = 1
    while que:
        v = que.popleft()
        for w in g[v]:
            if c[w] == 1:
                continue
            c[w] = 1
            que.append(w)

n, m  = MAP()
g = [[] for i in range(n)]
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = MAP()
    a[i] -= 1
    b[i] -= 1
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])

ans = 0
for i in range(m):
    g[a[i]].remove(b[i])
    g[b[i]].remove(a[i])
    c = [0]*n
    bfs()
    for j in range(n):
        if c[j] == 0:
            ans += 1
            break
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])

print(ans)

Submission status: Accepted

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

n,m=map(int,input().split())
pair=[i for i in range(n)]
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
    
def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

icnt=0
for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(m):
        if ii==i:
            continue
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
#    print(i,l)
    lenpair=len(set(l))    
    if lenpair!=1:
        icnt+=1

print(icnt)

Submission status: Accepted

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

par = [-1]*n
num = [0]*n

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

def union(x, y):
    p,q=find(x), find(y)
    if p==q:
        return
    if p>q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p

def size(x):
    return -par[find(x)]

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

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

ans=0

for i in range(m):
    L=lst[:i]+lst[i+1:]
    par=[-1]*n
    for l in L:
        union(l[0],l[1])
    if [p<0 for p in par].count(1)>1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
"""
何回も再帰するときはlimitを増やす
dfs
"""
import sys
sys.setrecursionlimit(200000)

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


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

bit = [0 for _ in range(n)]
def dfs(v):
    bit[v] = 1
    for j in tree[v]:
        if bit[j]==0:
            dfs(j)

ans = 0
for i in range(m):
    a,b = l[i]
    a -= 1
    b -= 1
    tree[a].remove(b)
    tree[b].remove(a)
    bit = [0 for _ in range(n)]
    dfs(a)
    if bit.count(1) !=n:
        ans += 1

    tree[a].append(b)
    tree[b].append(a)
print(ans)

Submission status: Accepted

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

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

def union(x,y):
    x,y=find(x),find(y)
    if x!=y:
        if x>y:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
M=[]
for i in range(m):
    x,y=map(int,input().split())
    M.append([x-1,y-1])

ans=0

for i in range(m):
    X=M[:i]+M[i+1:]
    par = [-1] * n
    for x in X:
        union(x[0],x[1])
    if [p<0 for p in par].count(1)>1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
t=[[0 for i in range(n)] for j in range(n)]
A,B=[],[]
for _ in range(m):
    a,b=map(int,input().split())
    A.append(a-1)
    B.append(b-1)
    t[a-1][b-1]=1
    t[b-1][a-1]=1
ans=0
for i in range(m):
    t[A[i]][B[i]]=0
    t[B[i]][A[i]]=0
    
    q=[0]
    visited={0}
    while q:
        temp=q.pop()
        for j in range(n):
            if j not in visited and t[temp][j]==1:
                q.append(j)
                visited.add(j)
    if len(visited)!=n: ans+=1
    t[A[i]][B[i]]=1
    t[B[i]][A[i]]=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self,N):
        #N個のノードのUnion-Find木を作成する
        self._parent = [n for n in range(0, N)]
        #グループのサイズ
        self._size=[1]*N
    def find_root(self,x):
        if self._parent[x]==x:
            return x
        self._parent[x]=self.find_root(self._parent[x])
        return self._parent[x]
    def unite(self, x, y):
        #xとyの属するグループを併合する
        gx=self.find_root(x)
        gy=self.find_root(y)
        if gx == gy:
            return
        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx]<self._size[gy]:
            self._parent[gx] = gy
            self._size[gy]+=self._size[gx]
        else:
            self._parent[gy]=gx
            self._size[gx]+=self._size[gy]
    def get_size(self, x):
        #xが属するグループのサイズ（個数）を返す
        return self._size[self.find_root(x)]
    def is_same_group(self, x, y):
        # xとyが同じ集合に属するか否か
        return self.find_root(x) == self.find_root(y)
    def calc_group_num(self):
        #グループ数を計算して返す
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans
n,m=list(map(int,input().split()))
#unionfindは併合はできるが結合はできない
ab=[]
for i in range(m):
    ab.append(list(map(int,input().split())))
ans=0
for i in range(m):
    union=UnionFindVerSize(n)
    for j in range(m):
        if i!=j:
          union.unite(ab[j][0]-1,ab[j][1]-1)
    if union.calc_group_num()!=1:
        ans=ans+1
        
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(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())
edges=[tuple(map(int,input().split())) for _ in range(M)]
count=0
for m in range(M):
  uf = UnionFind(N+1)
  for i in range(M):
    if m==i:continue
    a,b=edges[i]
    uf.unite(a,b)
  if len(uf.g)+Counter(uf.d)[-1]-1==2:count+=1
print(count)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    G = [[] for _ in range(N)]
    E = []
    for i in range(M):
        a,b = mi()
        a-=1; b -= 1 # 0-index

        G[a].append(b)
        G[b].append(a)
        E.append((a,b))
    
    deg1_v = -1
    for i in range(N):
        deg = len(G[i])
        if deg == 1:
            deg1_v = i
            break
    
    if deg1_v == -1:
        print(0)
        exit()

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

        visited_count = 0
        stack = deque([deg1_v])
        seen = set()
        visited = set()
        while stack:
            visited_count += 1
            current_e = stack.popleft()

            visited.add(current_e)
            for next in G[current_e]:
                if (current_e,next) in seen: continue
                stack.append(next)
                seen.add((current_e,next))
    
        if len(visited) != N:
            # print(a+1,b+1)
            ans += 1
    
        G[a].append(b)
        G[b].append(a)
    
    print(ans)





    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parent = [i for i in range(n)]
    self.height = [0 for i in range(n)]
        
  def get_root(self, i):
    if self.parent[i] == i:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]
            
  def unite(self, i, j):
    root_i = self.get_root(i)
    root_j = self.get_root(j)
    if root_i != root_j:
      if self.height[root_i] < self.height[root_j]:
        self.parent[root_i] = root_j
      else:
        self.parent[root_j] = root_i
        if self.height[root_i] == self.height[root_j]:
          self.height[root_i] += 1
                
  def is_in_group(self, i, j):
    if self.get_root(i) == self.get_root(j):
      return True
    else:
      return False
    
N, M = map(int, input().split())
graph = list()
ans = 0
for i in range(M):
  a, b = map(int, input().split())
  graph.append([a-1, b-1])
for i in range(M):
  flag = 0
  uf = UnionFind(N)
  for j in range(M):
    if(i != j):
      uf.unite(graph[j][0], graph[j][1])
  for k in range(1, N):
    if uf.is_in_group(0, k) == False:
      flag = 1
  if(flag == 1):
    ans += 1
print(ans)

Submission status: Accepted

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    flag=True
    for _i in range(n):
        if d[_i]==None:
            flag=False
    return flag

cnt=0
for i in range(m):
    graph = [[] for _ in range(n)]
    for j in range(m):
        if i!=j:
            graph[ab[j][0]-1].append(ab[j][1]-1)
            graph[ab[j][1]-1].append(ab[j][0]-1)
    if not bfs(0):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N, M = map(int, input().split())
edges = []
for _ in range(M):
    u, v = map(int, input().split())
    # 0-index
    edges.append([u-1, v-1])

# ある辺に着目したとき、それ以外の辺を一つずつグラフに追加し parents を更新する
# u <-> v を繋ぐ辺をグラフに追加した際、parents の u or v の親を更新する
# 全ての辺を繋ぎ終えたときの異なる親を数え、その値が 1 より多きければ着目したその辺は橋である


def root(u):
    if parents[u] < 0:
        return u
    parents[u] = root(parents[u])
    return parents[u]


def has_same_root(u, v):
    return root(u) == root(v)


def size(root_u):
    return -parents[root_u]


def unite(u, v):
    if has_same_root(u, v):
        return
    root_u = root(u)
    root_v = root(v)
    if size(root_u) > size(root_v):
        root_u, root_v = root_v, root_u
    parents[root_v] = root_u


ans = 0
for e_i in edges:
    parents = [-1 for _ in range(N)]
    for e_j in edges:
        if e_i == e_j:
            continue
        u, v = e_j
        unite(u, v)

    count = 0
    for i in range(N):
        if parents[i] < 0:
            count += 1
    if count > 1:
        ans += 1

print(ans)

Submission status: Accepted

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

# 全探索
N,M = map(int,readline().split())
G = [[] for i in range(N)]
bridges = [None] * M
for i in range(M):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  bridges[i] = (a - 1,b - 1)
  
ans = 0
for i in range(M):
  # 使わない橋を決める
  NG = bridges[i]
  seen = set()
  stack = []
  # 頂点, 親
  stack.append([0, -1])
  while stack:
    v,parent = stack.pop()
    if v in seen:
      continue
    seen.add(v)
    for child in G[v]:
      if child == parent:
        continue
      if (v, child) == NG or (child, v) == NG: # 今回使わない橋
        continue
      stack.append([child, v])
  if len(seen) != N:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy


N, M = map(int, input().split())
A = []
B = []

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


res = 0
for i in range(M):
    uni = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            uni.merge(A[j], B[j])
    # uniの連結成分を数える
    roots = [uni[x] for x in uni.root[1:]]
    counter = Counter(roots)
    if len(counter) > 1:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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 = map(int, readline().split())
    edge = list(list(map(int, readline().split())) for _ in range(M))
    bridge = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if i==j:
                continue
            else:
                uf.union(edge[j][0]-1, edge[j][1]-1)
        if uf.group_count()>1:
            bridge += 1
    print(bridge)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.height = [0]*n

    def get_root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]
        
    def unite(self, i, j):
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                if self.height[root_i] == self.height[root_j]:
                    self.height[root_i] += 1
    
    def is_in_group(self, i, j):
        if self.get_root(i) == self.get_root(j):
            return True
        else:
            return False



def main():
    import sys

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

    n, m = map(int, input().split())
    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a-1, b-1))
    
    cnt = 0
    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if i == j: continue
            a, b = edges[j]
            uf.unite(a, b)
        flag = 1
        for j in range(n):
            flag &= uf.is_in_group(0, j)
        if not flag: 
            cnt += 1
    print(cnt)
            
                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}
    
    #頂点の追加
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0
        
        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    #辺の追加
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)
        
        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]
            

    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])
        
    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()
            
    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.adjacent

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number
    
    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in G.vertex}

        if u==v:
            return 0
        
        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in G.vertex}

        if u==v:
            return 0
        
        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None

#連結成分の個数
def Connected_Component_Number(G):
    T={v:False for v in G.vertex}
    C=0
    for v in G.vertex:
        if not T[v]:
            X=G.connected_component(v)
            for x in X:
                T[x]=True
            C+=1
    return C
#---------------------------------------------------------------------
N,M=map(int,input().split())
G=Graph(list(range(1,N+1)))
E=[]
for _ in range(M):
    a,b=map(int,input().split())
    G.add_edge(a,b)
    E.append((a,b))

K=Connected_Component_Number(G)
X=0
for a,b in E:
    G.remove_edge(a,b)
    if Connected_Component_Number(G)!=K:
        X+=1
    G.add_edge(a,b)
print(X)

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*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.ranks[x]<self.ranks[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
        if self.ranks[x]==self.ranks[y]:
            self.ranks[x]+=1
    
    def number_of_class(self):
        return sum(x<0 for x in self.parents)
    
    def clear(self):
        self.parents=[-1]*n

n,m=map(int,input().split())
edge=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
g=Unionfind(n)
ans=0
for e in edge:
    g.clear()
    for f in edge:
        if f!=e:
            g.union(f[0],f[1])
    if g.number_of_class()>1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

read=sys.stdin.read

n,m=map(int,input().split())
edge=[tuple(map(int,lst.split())) for lst in read().splitlines()]


def isconn(v,e0):
  clst=[1]*(n+1)
  clst[v]=0
  for _ in range(n):
    for e in edge:
      if e!=e0:
        tmp=clst[e[1]]&clst[e[0]]
        clst[e[1]]=tmp
        clst[e[0]]=tmp
  if sum(clst)>1:
    return False
  else:
    return True
ans=0
for e in edge:
  if not isconn(1,e):
    ans+=1
print(ans)

Submission status: Accepted

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

ans = 0

def dfs(queue, a, b):
    while len(queue) != 0:
        x = queue.popleft()
        for i in range(len(graph[x])):
            if (min(graph[x][i], x) != a or max(x, graph[x][i]) != b) and visited[graph[x][i]] == 0:
                queue.append(graph[x][i])
                visited[graph[x][i]] = 1

for i in range(m):
    visited = [0] * n
    visited[0] = 1
    queue = deque()
    queue.append(0)
    dfs(queue, data[i][0], data[i][1])
    if sum(visited) != n:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def dfs(cur):
    visited[cur] = 1
    for nx in range(n):
        if G[cur][nx] == 0:
            continue
        if visited[nx]:
            continue
        dfs(nx)


n, m = map(int, input().split())
G = [[0]*n for _ in range(n)]
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append((a-1, b-1))
    G[a-1][b-1] = G[b-1][a-1] = 1
ans = 0
for a, b in ab:
    G[a][b] = G[b][a] = 0
    visited = [0]*n
    dfs(0)
    if not all(visited):
        ans += 1
    G[a][b] = G[b][a] = 1

print(ans)

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    exceptions = []
    for _ in range(m):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
        exceptions.append((a-1, b-1))

    ans = 0
    for from_, to in exceptions:
        res = dfs(n, edges, exception={(from_, to), (to, from_)})
        if not res:
            ans += 1
    print(ans)


def dfs(nodes, edges, exception):
    seen = [False] * nodes
    todo = [0]
    while todo:
        node = todo.pop()
        if seen[node]:
            continue
        seen[node] = True

        for to in edges[node]:
            if (node, to) in exception:
                continue
            todo.append(to)

    return sum(seen) == nodes


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#dfs renshuu
from collections import defaultdict

def dfs(x):
  if f[x] == 1: return
  f[x]=1
  for nex in dd[x]:
    if x==a and nex==b: continue
    dfs(nex)

n,m=map(int,input().split())
dd=defaultdict(list)
lst=[]
ans=0
for i in range(m):
  a,b=map(int,input().split())
  lst.append((a,b,))
  dd[a].append(b)
  dd[b].append(a)
for a,b in lst:
  f=[0]*(n+1)
  dfs(a)
  if f[b]!=1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# 条件下の「橋」を、「エッジを1つしか持たないノード」から
#「エッジを3つ以上持つノード」の間にあるエッジと考える
from collections import defaultdict

def remove_checked():
  global check_nodes,dd
  for n in check_nodes:
    if n in dd:
      dd.pop(n)
    for k in dd:
      if n in dd[k]:
        dd[k].remove(n)
  check_nodes=set()        

n,m=map(int,input().split())
dd=defaultdict(list)
check_nodes=set()
for i in range(m):
  a,b=map(int,input().split())
  dd[a].append(b)
  dd[b].append(a)

cnt=0
while True:
  for k in dd.keys():
    if k in check_nodes:
      continue
    nodes=dd[k]
    if len(nodes) == 1:
      nxt=k
      while len(nodes) <= 2:
        check_nodes.add(nxt)
        cnt+=1
        nxt=nodes[0]
        if nxt in check_nodes:
            nxt = nodes[1]
        nodes=dd[nxt]
        if len(nodes) == 1:
          check_nodes.add(nxt)
          break
  if check_nodes==set():
    break
  remove_checked()

print(cnt)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
d=[[]for _ in range(n+1)]
c=[]
for _ in range(m):
    a,b=f()
    d[a]+=[b]
    d[b]+=[a]
    c+=[[a,b]]
ans=0
for i,j in c:
    a=[0]*(n+1)
    b=list(d[i])
    b.remove(j)
    now=0
    while b:
        now=b.pop(0)
        if a[now]==0:
            a[now]+=1
            for k in d[now]:
                if a[k]==0 and k!=i:
                    b+=[k]
    if a[j]==0:
        ans+=1
print(ans)