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 collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    edge = []
    answer = 0
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
        edge.append([a, b])
    for ng in edge:
        ng.sort()
        visited = [0 for _ in range(n)]
        q = deque([0])
        while q:
            now = q.pop()
            if visited[now] == 0:
                visited[now] = 1
                for next_v in g[now]:
                    if ng != sorted([next_v, now]):
                        q.append(next_v)
        if sum(visited) < n:
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N, M = map(int, input().split())
AB = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(M)]

ans = 0
for i in range(M):
    tree = UnionFind(N)
    for a, b in (AB[:i] + AB[i + 1:]):
        tree.union(a, b)
    if tree.getComponent() > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
chk = []
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    chk.append((u,v))
chk = tuple(chk)

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
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

ans = 0
for i in range(m):
  par = [-1]*n
  for j in range(m):
    if i == j:
      continue
    else:
      unite(chk[j][0],chk[j][1])
  if size(0) != n:
    ans += 1
    
print(ans)

Submission status: Accepted

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

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

    def unite(self,x,y): 
        return self.link(self.findSet(x), self.findSet(y))

    def link(self,x,y):
        if self.rank[x] > self.rank[y]: 
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]: self.rank[y] += 1

    def findSet(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.findSet(self.parent[x])
        return self.parent[x]

n,m = map(int,input().split())
ans = 0
edge = [[int(i)-1 for i in input().split()] for _ in range(m)]
for i in range(m):
    ds = DisjointSet(n)
    for j in range(m):
        if j == i: continue
        a,b = edge[j]
        ds.unite(a,b)
    for j in range(1,n):
        if not ds.same(0,j):
            ans += 1
            break
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
e = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    e.append((a,b))
ans = m
seen = [False]*n
q = deque()
for i in range(m):
    a,b = e[i]
    q.clear()
    q.append((a,-1))
    for j in range(n): seen[j] = False
    flag = True
    while q and flag:
        cur,prev = q.popleft()
        seen[cur] = True
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            q.append((nxt,cur))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def bfs(s, n, g):
    dist = [-1] * n
    dist[s] = 0
    que = deque([])
    que.append(s)
    while que:
        v = que.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue  # すでに探索している時はスルー
            dist[nv] = dist[v] + 1
            que.append(nv)
    if -1 in dist:
        return True
    else:
        return False


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    gg = []
    for _ in range(m):
        a, b = [int(i) - 1 for i in input().split()]
        g[a].append(b)
        g[b].append(a)
        gg.append((a, b))
    ans = 0
    for a, b in gg:
        g[a].remove(b)
        g[b].remove(a)
        if bfs(0, n, g):
            ans += 1
        g[a].append(b)
        g[b].append(a)
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline


def bfs(s, n, g):
    dist = [-1] * n
    dist[s] = 0
    que = deque([])
    que.append(s)
    while que:
        v = que.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v] + 1
            que.append(nv)
    if -1 in dist:
        return True
    else:
        return False


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    gg = []
    for _ in range(m):
        a, b = [int(i) - 1 for i in input().split()]
        g[a].append(b)
        g[b].append(a)
        gg.append((a, b))
    ans = 0
    for a, b in gg:
        g[a].remove(b)
        g[b].remove(a)
        if bfs(0, n, g):
            ans += 1
        g[a].append(b)
        g[b].append(a)
    print(ans)
    return


if __name__ == "__main__":
    main()

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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
ans=0
for i in range(m):
    uf=UnionFind(n)
    for j in range(m):
        if j==i:
            continue
        else:
            uf.union(a[j][0]-1,a[j][1]-1)
    if not uf.same(a[i][0]-1,a[i][1]-1):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in range(m):
  graph = [list() for i in range(n+1)]
  visited = [True]+[False] * (n)
  for k,(a,b) in enumerate(ab):
    if k == i:
      continue
    graph[a].append(b)
    graph[b].append(a)
  NEXT = [1]
  while len(NEXT):
    now = NEXT.pop()
    for j in graph[now]:
      if not visited[j]:
        visited[j] = True
        NEXT.append(j)
  if not all([j for j in visited]):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist


N, M = MAP()
L = [LIST() for i in range(M)]
graph = defaultdict(list)

for a, b in L:
    graph[a-1].append((b-1, 1))
    graph[b-1].append((a-1, 1))

ans = 0

for i in range(M):
    a, b = L[i]
    E = deepcopy(graph)
    E[a-1].remove((b-1, 1))
    E[b-1].remove((a-1, 1))
    dist = dijkstra(E, 0)
    if dist.count(INF) > 0:
        ans += 1

print(ans)

Submission status: Accepted

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

graph = [[False] * N for _ in range(N)]
for a, b in X:
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True


def dfs(u):
    visited[u] = True
    for v in range(N):
        if visited[v] or not graph[u][v]:
            continue
        dfs(v)


res = 0
for i in range(M):
    a, b = X[i]
    a -= 1
    b -= 1
    
    graph[a][b] = False
    graph[b][a] = False
    
    visited = [False] * N
    dfs(0)
    res += int(not all(visited))
    
    graph[a][b] = True
    graph[b][a] = True
    
print(res)

Submission status: Accepted

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

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

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

cnt = 0
for i in range(M):
    par = list(range(N + 1))
    rank = [0] * (N + 1)
    for j, (u, v) in enumerate(X):
        if i == j:
            continue
        unite(u, v)
    
    res = True
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            res &= find(j) == find(k)

    cnt += int(not res)
        
print(cnt)

Submission status: Accepted

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

ans = 0
pre = [-1]*n
low = [-1]*n
 
def dfs(v,p,a):
	global ans
	if pre[v] != -1:
		low[a] = min(low[a],low[v])
		return low[a]
	pre[v] = p
	low[v] = p
	for u in links[v]:
		if u == a:
			continue
		low[v] = min(low[v],dfs(u,p+1,v))
	if pre[v] == low[v]:
		ans += 1
	return low[v]
 
dfs(0,0,None)
print(ans-1)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self,n):
        #par[x]==xならxというノードが根。xに親がいない
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1) 
    
    def find(self,x): #xの根を検索
        #xが根ならxを返す
        if self.par[x] == 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[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1 #rankが同じ木を繋げたとき根のランクを一つ上げる
    
    def same_check(self,x,y): #xとyが同じ集合に属しているか
        return self.find(x) == self.find(y)
        
n, m = map(int,input().split())
A=[list(map(int,input().split())) for i in range(m)]
ans = 0
for i in range(m):
    uf = UnionFind(n) #
    for j in range(m):
        if i != j: #
            uf.unite(A[j][0],A[j][1])
    f = 1
    g = uf.find(1) #
    for j in range(1,n+1):
        if g != uf.find(j): #1~n(iを除く)がすべて同じ集合に属しているか
            f = 0
            break
    if not f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

graph = defaultdict(list)
for a, b in L:
    graph[a-1].append((b-1, 1))
    graph[b-1].append((a-1, 1))

ans = 0
for a, b in L:
    E = deepcopy(graph)
    E[a-1].remove((b-1, 1))
    E[b-1].remove((a-1, 1))
    d = dijkstra(E, a-1)
    if d[b-1] == INF:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
N,M = map(int,input().split())
edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0]*(N+1) for _ in range(N+1)]
# 連結している部分は1
for a,b in edge:
    graph[a][b] = 1
    
answer = 0
INF = 10 ** 9
for a,b in edge:
    graph[a][b] = INF
    # directed = False : 無向グラフ
    # indices = a : 始点
    # distはaからスタートしてそれぞれの点にたどり着くまでの最短距離
    dist = dijkstra(graph, indices = a, directed = False)
    if dist[b] >= INF:
        answer += 1
    graph[a][b] = 1
 
print(answer)

Submission status: Accepted

Solution code:
import sys

n, m, *ab = map(int, sys.stdin.read().split())
graph = [set() for _  in range(n)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1; b -= 1
    graph[a].add(b); graph[b].add(a)

def main():
    stack = [i for i in range(n) if len(graph[i]) == 1]
    bridges = 0
    while stack:
        x = stack.pop()
        if not graph[x]: continue
        y = graph[x].pop()
        graph[y].remove(x)
        bridges += 1
        if len(graph[y]) == 1:
            stack.append(y)
    print(bridges)

if __name__ ==  '__main__':
    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())
E = []
for _ in range(M):
  a, b = map(int, input().split())
  E.append((a-1, b-1))
ans = 0
r = 0
while r < M:
  uf = UnionFind(N)
  i = 0
  while i < M:
    if i != r:
      a, b = E[i]
      uf.union(a, b)
    i += 1
  i = 0
  while i < N:
    _ = uf.find(i)
    i += 1
  if uf.group_count() > 1:
    ans += 1
  r += 1
print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

limit=50
graph=[[False]*limit for _ in range(limit)]
visited=[False]*limit

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

def main():
  n,m=LI()
  a=[[] for _ in range(n*n)]
  b=[[] for _ in range(n*n)]
  for i in range(m):
    _a,_b=LI()
    _a-=1
    _b-=1
    a[i]=_a
    b[i]=_b
    graph[_a][_b]=True
    graph[_b][_a]=True

  ans=0
  for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False

    for j in range(n):
      visited[j]=False
    dfs(n,0)
    no_visited=False
    for j in range(n):
      if visited[j]==False:
        no_visited=True
    if no_visited:
      ans+=1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True

  return ans

# main()
print(main())

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**8)

def dfs(v, es):
    #print(h,w)
    if len(es[v])==0:
        return 0
    for u in es[v]:
        if visited[u]==False:
            visited[u]=True
            dfs(u,es)
    return 0

import copy
ans = 0
for i in range(M):
    visited = [False]*N
    a,b = edges[i]
    es = copy.deepcopy(edge)
    # print(edge,a,b)
    es[a].remove(b)
    es[b].remove(a)
    for v in range(N):
        if visited[v]==False:
            visited[v]=True
            dfs(v,es)
            if False in visited:
                # print(a,b)
                break
    else:
        continue
    ans += 1
print(ans)

Submission status: Accepted

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

def dfs(n, point):
    for m in L[n]:
        if point[m] == 1:
            continue
        else:
            point[m] = 1
            dfs(m, point)

for i in range(m):
    L = [[] for _ in range(n + 1)]
    point = [0]*(n+1)

    for j in range(len(list_AB)):
        a = list_AB[j][0]
        b = list_AB[j][1]
        if i != j:
            L[a].append(b)
            L[b].append(a)
    point[1] = 1
    dfs(1, point)

    if sum(point) != n:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

maxn = 100000

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

par = [0] * n
rank = [0] * n

#初期化
for i in range(n):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

a = [0] * m
b = [0] * m
for i in range(m):
    a[i],b[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
    
ans = 0
for i in range(m):
    for j in range(n):
        par[j] = j
        rank[j] = 0
        
    for j in range(m):
        if i == j:
            continue
        unite(a[j],b[j])
        
    l = [find(k) for k in range(n)]
    fl = 1
    
    for j in range(n-1):
        if l[j] != l[j+1]:
            fl = 0
            
    if fl == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    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]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # 要素xが属するグループのサイズ（要素数）を返す
    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 group_count(self):
        return len(self.roots())

    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = map(int, input().split())
l = []
for i in range(M):
    array = list(map(int, input().split()))
    l.append(array)

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i!=j:
            uf.union(l[j][0]-1,l[j][1]-1)
    if uf.group_count() == 2:
        ans+=1
    
print(ans)

Submission status: Accepted

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


def dfs(v, remove):
    for u in tree[v]:
        if u not in visited and [v, u] != remove and [u, v] != remove:
            visited.add(u)
            dfs(u, remove)


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

res = 0
for a, b in k:
    visited = set()
    dfs(0, [a, b])
    if len(visited) < n:
        res += 1
print(res)

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

ans = 0
for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i==j:
      continue
    uf.union(E[j][0]-1, E[j][1]-1)
  if uf.group_count()>1:
    ans += 1
print(ans)

Submission status: Accepted

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


# 橋となる辺を返す
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


print(len(bridge(tree, n)))

Submission status: Accepted

Solution code:
def find(x):
    if parents[x]==x:
        return x
    return find(parents[x])

def unite(x,y):
    px=find(x)
    py=find(y)
    if deepth[px]>deepth[py]:
        parents[py]=px
        deepth[px]=max(deepth[px],deepth[py]+1)
    else:
        parents[px]=py
        deepth[py]=max(deepth[py],deepth[px]+1)

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

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

cnt=0
for i in range(M):
    flag=True
    parents=[i for i in range(N)]
    deepth=[0 for _ in range(N)]
    for k in range(M):
        if i!=k:
            unite(Graph[k][0],Graph[k][1])
    for l in range(N-1):
        if find(l)!=find(l+1):
            flag=False
    if not flag:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
path = [[] for _ in range(n)]
ab = [[] for _ in range(m)]
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab[i] = (a,b)
  path[a].append(b)
  path[b].append(a)
def dfs(a,b):
  que = deque()
  reach = [False]*n
  reach[0] = True
  que.append(0)
  while que:
    p = que.pop()
    for i in path[p]:
      if (p,i)!=(a,b)!=(i,p) and not reach[i]:
        que.append(i)
        reach[i] = True
  return reach != [True] * n
ans = 0
for a,b in ab:
  ans += dfs(a,b)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

abm = [None] * m
for i in range(m):
    abm[i] = list(map(int, input().split(' ')))

def check(i):
    cl = [False] * n
    edges = abm[:i] + abm[i + 1:]
    d = deque([1])

    def bfs():
        while True:
            if not d:
                return
            
            v = d.popleft()
            if cl[v - 1]:
                continue
            else:
                cl[v - 1] = True

                nxts = [edge[0] for edge in edges if edge[1] == v]
                for nxt in nxts:
                    d.append(nxt)

                nxts = [edge[1] for edge in edges if edge[0] == v]
                for nxt in nxts:
                    d.append(nxt)

    bfs()

    if cl.count(False):
        return True
    else:
        return False

count = 0
for i in range(m):
    if check(i):
        count += 1
print(count)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    from scipy.sparse.csgraph import connected_components  # https://note.nkmk.me/python-scipy-connected-components/
    from scipy.sparse import csr_matrix
    
    N, M = map(int, input().split())  # 頂点数、辺数
    A, B, C = [0] *  M, [0] * M, [1] * (M-1)
    for i in range(M):
        A[i], B[i] = map(int, input().split())
        A[i]-=1
        B[i]-=1
    
    cnt = 0
    for i in range(M):
        #print(B[:i] + B[i + 1:i + M] + B[i + M + 1:])
        #print(A[:i] + A[i + 1:i + M] + A[i + M + 1:])
        csr = csr_matrix((C, (A[:i] + A[i + 1:], B[:i] + B[i + 1:])), shape=(N, N))
        #print(csr)
        #print('haha')
        n, labels = connected_components(csr)
        if n == 2:
           cnt += 1
    print(cnt)


resolve()