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 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):
    csr = csr_matrix((C, (A[:i] + A[i + 1:], B[:i] + B[i + 1:])), shape=(N, N))
    n, labels = connected_components(csr)
    if n == 2:
       cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M=map(int, input().split())
S=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int, input().split())
  S[a-1].append((i,b-1))
  S[b-1].append((i,a-1))
  
def dfs(start, goal, exclude):
  for i,b in S[start]:
    if i==exclude or (b in dones):
      continue
    if b==goal:
      dones.append(b)
      break
    else:
      dones.append(b)
      dfs(b,goal,exclude)
  if goal not in dones:
    return True
ans=[]
for i in range(N):
  #m番目の辺について考える
  for m,b in S[i]:
    dones=[]
    is_bridge=dfs(i,b,m)
    #print(is_bridge)
    if is_bridge and m not in ans:
      ans.append(m)
      
print(len(ans))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 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 = [list(map(int_, input().split())) for _ in range(M)]
ans = 0
for ng in range(M):
    uf = UnionFind(N)
    for i in range(M):
        if i != ng:
            uf.union(*ablist[i])
    if len(uf.roots()) >= 2:
        ans += 1
print(ans)

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

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for k in range(M):
        if i == k:
            continue
        uf.union(graph[k][0]-1,graph[k][1]-1)
    if uf.group_count() != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq

#Union-Find
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())



#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

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

#print(AB)

for i in range(M):
  uf = UnionFind(N)
  for j in range(M):
    if(i==j):
      pass
    else:
      uf.union(AB[j][0]-1, AB[j][1]-1)
  #print(uf.size(0))
  if(uf.size(0)!=N):
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

def dfs(mat,v):
    seen[v]+=1
    for pv in mat[v]:
        if seen[pv]:
            continue
        dfs(mat,pv)

ans=0
arr=[]
for i in range(m):
    x,y=mii()
    arr.append([x-1,y-1])

for i in range(m):
    seen=[0]*n
    mat=[[] for _ in range(n)]
    for j,k in enumerate(arr):
        if i!=j:
            a,b=k
            mat[a].append(b)
            mat[b].append(a)
    dfs(mat,1)
    if sum(seen)!=n:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    g = [[False] * N for i in range(N)]
    bridge = []
    for i in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        bridge.append((a,b))
        g[a][b] = True
        g[b][a] = True
    
    ans = 0
    for a, b in bridge:
        visited = [False] * N
        g[a][b] = False
        g[b][a] = False
        if not dfs(0,g,visited,N):
            ans += 1

        g[a][b] = True
        g[b][a] = True
    
    print(ans)

def dfs(now, g, visited, N):
    visited[now] = True
    if isAllVisited(visited):
        return True
    
    for next in range(N):
        if g[now][next] and not visited[next]:
            if dfs(next, g, visited, N):
                return True
    
    return False

def isAllVisited(visited):
    for v in visited:
        if not v:
            return False
    
    return True

if __name__ == '__main__':
    solve()

Submission status: Accepted

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


def func(n):
    seen[n]=True
    for val in lst[n]:
        if seen[val] == False:
            todo.append(val)
    if todo:
        func(todo.pop(-1))
    else:
        return None

count=0
for edge_to_check in ab:
    lst = [[] for _ in range(N+1)]
    seen = [False] * (N + 1)
    todo = []
    for el in ab:
        if el != edge_to_check:
            lst[el[0]].append(el[1])
            lst[el[1]].append(el[0])
    #print(lst)
    # DFS
    func(1)
    #print(edge_to_check, seen)
    if seen.count(False) > 1:
        count+=1
print(count)

Submission status: Accepted

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

g = [[] for i in range(n+1)]
e = []

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

def dfs(start, end):
    q = []
    q.append(start)
    
    while q:
        cur = q.pop()
        v[cur] = 1
        
        if cur == end:
            return True
        
        for next_v in g[cur]:
            if v[next_v] != 1 and (cur, next_v) != (start, end):
                q.append(next_v)
    
    return False

ans = 0

for a,b in e:
    v = [0]*(n+1)
    if not dfs(a,b):
        ans += 1

print(ans)

Submission status: Accepted

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

g = [[] for i in range(n + 1)]
v = [0] * (n + 1)
e = []
for i in range(m):
    a, b = map(int, input().split())
    e.append((a, b))
    g[a].append(b)
    g[b].append(a)

def dfs(start, end):
    q = []
    q.append(start)

    while q:
        # 現在位置curをスタックに追加
        cur = q.pop()
        # 訪れた場所として記録
        v[cur] = 1

        if cur == end:
            return True

        # 繋がっている頂点next_vをまだ訪れていなければ、qに追加
        # (cur, next_v) != (start, end)は、辺になっていなければ、つまり一旦他の頂点を経由して目的地にたどり着いてしまった場合...
        for next_v in g[cur]:
            if v[next_v] != 1 and (cur, next_v) != (start, end):
                q.append(next_v)
    return False

ans = 0
for a,b in e:
    v = [0] * (n + 1)
    if not dfs(a,b):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []

for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])

def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [0 for i in range(n)]

    for ar in arr:
        nodeFrom = ar[0] - 1
        nodeTo = ar[1] - 1
        nodes[nodeFrom].append(nodeTo)
        nodes[nodeTo].append(nodeFrom)

    return nodes, nodeStates


def bfs(startNodeIndex, arr, nodeStates):
    q = deque()

    q.append(startNodeIndex)
    nodeStates[startNodeIndex] = 1

    while q.__len__() > 0:
        nodeIndex = q.popleft()
        childNodes = arr[nodeIndex]
        for childNodeIndex in childNodes:
            if nodeStates[childNodeIndex] == 0:
                q.append(childNodeIndex)
                nodeStates[childNodeIndex] = 1

    return nodeStates


def calculate(n, m, arr):
    arr = list(arr)

    result = 0

    for ar in arr:
        brr = arr.copy()
        brr.remove(ar)

        nodes, nodeStates = prepare(n, m-1, brr)
        nodeStates = bfs(0, nodes, nodeStates)

        if sum(nodeStates) != n:
            result = result + 1

    print(result)



calculate(N, M, ARR)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=[]
M=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a-1,b-1])
    M[a-1].append(b-1)
    M[b-1].append(a-1)
ans=0
 
def dfs(x,se):
    visited[x]=1
    for m in M[x]:
        if se!={x,m} and visited[m]==0:
            dfs(m,se)
 
for i in range(m):
    visited=[0]*n
    dfs(0,set(X[i]))
    if 0 in visited:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
D = {i: [] for i in range(N)}
for i in edges:
  i[0] -= 1
  i[1] -= 1
  D[i[0]].append(i[1])
  D[i[1]].append(i[0])
cnt = 0
L = [0 for _ in range(N)]
base = [1 for _ in range(N)]
for i in edges:
  L[0] = 1
  p = [0]
  f = [i[0], i[1]]
  while p != []:
    n = len(p)
    for j in range(n):
      X = D[p[j]][:]
      for k in X:
        if L[k] == 0 and (p[j] != f[1] or k != f[0]) and (p[j] != f[0] or k != f[1]):
          L[k] = 1
          p.append(k)
    p = p[n:]
  if L != base:
    cnt += 1
  L = [0 for _ in range(N)]
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
N, M = list(map(int, input().split()))

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

ans = 0

for m in range(M):
    count = 0
    T = defaultdict(list)
    for a, b in AB:
        if count == m:
            bridge = (a, b)
            count += 1
            continue
        T[a].append(b)
        T[b].append(a)
        count += 1

    q = deque()
    q.append(bridge[0])

    visited = [False] * N

    flg = True
    while q:
        c = q.popleft()
        visited[c] = True
        if c == bridge[1]:
            flg = False
            break
        for t in T[c]:
            if not visited[t]:
                q.append(t)
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []
for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])



def prepare(n, m, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [0 for i in range(n)]
    for i in range(m):
        nodeFrom = arr[i][0] - 1
        nodeTo = arr[i][1] - 1
        nodes[nodeFrom].append(nodeTo)
        nodes[nodeTo].append(nodeFrom)

    return nodes, nodeStates


nodes, nodeStates = prepare(N, M, ARR)


def dfs(currentNodeIndex, arr, nodeStates):
    if nodeStates[currentNodeIndex] == 0:
        nodeStates[currentNodeIndex] = 1

    childNodes = arr[currentNodeIndex]
    for childNodeIndex in childNodes:
        if nodeStates[childNodeIndex] == 0:
            dfs(childNodeIndex, arr, nodeStates)

    return nodeStates


# dfs(0, nodes)


def calculate(n, m, arr):
    arr = list(arr)
    result = 0
    for ar in arr:
        brr = arr.copy()
        brr.remove(ar)
        nodes, nodeStates = prepare(n, m-1, brr)
        nodeStatesResult = dfs(0,nodes,nodeStates)
        if sum(nodeStatesResult) != n:
            result = result + 1
    print(result)


calculate(N,M,ARR)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
import copy
def bfs(graph,s,g):
    que = [s]
    visited = []
    while len(que)>0:
        label = que.pop(0)
        for nv in graph[label]:
            if nv == g:
                return 1
            if nv not in visited:
                visited.append(nv)
                que.append(nv)
    return 0

def main():
    graph = {}
    for i in range(n):
        graph[i] = []
    for _ in range(m):
        s,g = map(int,input().split())
        graph[s-1] += [g-1]
        graph[g-1] += [s-1]

    ans = 0
    for i in range(n):
        for k in graph[i]:
            g = copy.copy(graph)
            if k>i:
                g[i] = list(set(g[i])-set([k]))
                if bfs(g,i,k)==0:
                    ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, 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


N, M = map(int, input().split())
edge = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

cnt = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(edge):
        if j == i:
            continue
        else:
            uf.union(a - 1, b - 1)
    if uf.parents[uf.find(0)] != -N:
        cnt += 1

print(cnt)

Submission status: Accepted

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

def dfs(v,seen):
    if seen[v]: return
    seen[v] = True
    for nv in G[v]:
        dfs(nv,seen)

cnt = 0

for i in range(m):
    ra,rb = data[i]
    G[ra].remove(rb)
    G[rb].remove(ra)
    seen = [False]*n
    dfs(0,seen)
    cnt += (sum(seen) != n)
    G[ra].append(rb)
    G[rb].append(ra)

print(cnt)

Submission status: Accepted

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

def dfs(x,se):
    visited[x]=1
    for m in M[x]:
        if se!={x,m} and visited[m]==0:
            dfs(m,se)


for i in range(m):
    visited=[0]*n
    dfs(0,set(X[i]))
    if 0 in visited:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
X=[]
M=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a,b])
    M[a-1].append(b-1)
    M[b-1].append(a-1)
ans=0
for i in range(m):
    se={X[i][0]-1,X[i][1]-1}
    q=deque([0])
    visited=[0]*n
    while q:
        s=q.popleft()
        if visited[s]==1:
            continue
        visited[s]=1
        for x in M[s]:
            if {s,x}!=se:
                q.append(x)
    if sum(visited)!=n:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
X=[]
M=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a,b])
    M[a-1].append(b-1)
    M[b-1].append(a-1)
ans=0
for i in range(m):
    a,b=X[i][0],X[i][1]
    M[a-1].remove(b-1)
    M[b-1].remove(a-1)
    q=deque([0])
    visited=[0]*n
    while q:
        s=q.popleft()
        if visited[s]==1:
            continue
        visited[s]=1
        for x in M[s]:
            q.append(x)
    M[a-1].append(b-1)
    M[b-1].append(a-1)
    if sum(visited)!=n:
        ans+=1
print(ans)

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

      
n,m = map(int,input().split())
a_b_list = []
for i in range(m):
  a_b_list.append(list(map(int,input().split())))
  
count = 0
for i in range(m):
  a_b_copy = a_b_list.copy()
  uf = UnionFind(n)
  a_b_copy.pop(i)
  for a_b in a_b_copy:
    uf.union(a_b[0]-1,a_b[1]-1)
  if uf.group_count() != 1:
    count+= 1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[ [0 for _ in range(50)] for _ in range(50)]
a=[0]*m
b=[0]*m
for i in range(m):
    a[i],b[i]=map(lambda x:int(x)-1,input().split())
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
ans=0
#print(g)
for i in range(m):
#    print(i,end=' start i \n')
    g[a[i]][b[i]]=0
    g[b[i]][a[i]]=0
    vis=[0]*n
    def dfs(u):
        vis[u]=1
#        print(u,end=' dfs\n')
        for j in range(n):
            if j!=u and g[u][j]==1 and vis[j]==0:
                dfs(j)
    bridge=False
    dfs(0)
    for j in range(n):
        #print(i,vis)
        if vis[j]==0:
            bridge=True
    if bridge:
        ans+=1
    #print(i,end=' curr i \n')
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n

    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

    def size(self,x):
        return self.tsize[self.root(x)]

def main():
    n,m = tuple([int(t)for t in input().split()])

    t = [tuple([int(t)-1 for t in input().split()])for _ in [0]*m]

    ans = 0
    for k in range(m):
        uf = UnionFind(n)
        for i in range(m):
            if k!=i:
                uf.unite(t[i][0],t[i][1])
        if uf.size(0) !=n :ans+=1
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n

    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

    def size(self,x):
        return self.tsize[self.root(x)]

def main():
    n,m = tuple([int(t)for t in input().split()])

    t = [tuple([int(t)-1 for t in input().split()])for _ in [0]*m]

    ans = 0
    for k in range(m):
        uf = UnionFind(n)
        for i in range(m):
            if k!=i:
                uf.unite(t[i][0],t[i][1])
        if uf.size(0) !=n :ans+=1
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
ans = 0
for i in s:
    l = list(range(n))
    for j in s:
        if i!=j:
            l=[l[j[0]-1] if l[k]==l[j[1]-1] else l[k] for k in range(n)]
    if len(set(l))!=1: ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
E=[[] for _ in range(N)]
lst=[]
for i in range(M):
  x,y=map(int,input().split())
  x-=1
  y-=1
  E[x].append(y)
  E[y].append(x)
  lst.append((x,y))
cnt=0
for x,y in lst:
  stack=[0]
  seen=[0]*N
  seen[0]=1
  while stack:
    u=stack.pop()
    for v in E[u]:
      if (u==x and v==y)or (u==y and v==x):
        pass
      else:
        if seen[v]==0:
          seen[v]=1
          stack.append(v)
  if sum(seen)==N:
    pass
  else:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:

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

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

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

    def unite(self, x, y):
        if self.isSame(x, y):
            return
        x, y = self.find(x), self.find(y)

        if self.d[x] > self.d[y]:
            self.p[x] += self.p[y]
            self.p[y] = x
        else:
            self.p[y] += self.p[x]
            self.p[x] = y
            if self.d[x] == self.d[y]:
                self.d[y] += 1

    def numTree(self):
        return sum([1 for p in self.p if p < 0])


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

ans = 0
for i in range(M):
    U = UnionFind(N)
    for a, b in E[:i] + E[i + 1:]:
        U.unite(a - 1, b - 1)
    if U.numTree() == 2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
icase=0
if icase==0:
    n,m=map(int, input().split())
    a=[]
    b=[]
    for i in range(m):
        ai,bi=map(int, input().split())
        a.append(ai)
        b.append(bi)
elif icase==1:
    n=6
    m=5
#    a=[[1],[2],[3],[4],[5]]
#    b=[[2],[3],[4],[5],[6]]
    a=[1,2,3,4,5]
    b=[2,3,4,5,6]
elif icase==2:
    n=7
    m=7
    a=[1,2,3,4,4,5,6]
    b=[3,7,4,5,6,6,7]

    
vtx=[]
for i in range(n):
    vtx.append([i+1])
icnt=0

for j in range(m):    
    vtx1=vtx.copy()
    a1=a.copy()
    b1=b.copy()
    del a1[j]
    del b1[j]
    
    for i in range(m-1):
        for v1 in vtx1:
            if a1[i] in v1:
                if not b1[i] in v1:
                    for v2 in vtx1:
                        if v1!=v2:
                            if b1[i] in v2:
                                break
                    vtx1.remove(v1)
                    vtx1.remove(v2)
                    v3=v1+v2
                    vtx1.append(v3)
#        print(a[i],b[i],len(vtx1),vtx1)
#    print(len(vtx1),vtx1)
    if len(vtx1)!=1:
        icnt=icnt+1
print(icnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split()))for _ in range(M)]

    result = 0

    for i in AB:
        b = AB[:]
        start = i[0]
        goal = i[1]
        b.remove(i)
        q = deque()
        q.append(start)

        searched = {start}
        while q:
            current = q.popleft()
            if current == goal:
                break
            for j in b:
                if current == j[0] and j[1] not in searched:
                    q.append(j[1])
                    searched.add(j[1])
                elif current == j[1] and j[0] not in searched:
                    q.append(j[0])
                    searched.add(j[0])
        else:
            result += 1

    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import accumulate

N, M = map(int, input().split())


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

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

    if x == y:
        return
    if x > y:
        x, y = y, x

    parents[x] += parents[y]
    parents[y] = x    

def same(x,y):

    return find(x) == find(y)

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

for i in range(M):
    parents = [-1] * N
    tmp1, tmp2 = edges[i]
    for j in range(M):
        if i == j: continue
        a,b = edges[j]
        union(a,b)

    if not same(tmp1, tmp2):
        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)]

def dfs(num):
    temp = [num]
    visited = [0]*N
    
    while temp:
        p = temp.pop()
        for i in ab[p]:
            if visited[i] == 0:
                visited[i] = 1
                temp.append(i)
    if sum(visited)==N: jdg = False
    else: jdg = True
    return jdg

ans = 0 
for a,b in AB:
    ab = [[] for _ in range(N)]
    for a1, b1 in AB:
        if a1==a and b1==b:continue
        ab[a1-1].append(b1-1)
        ab[b1-1].append(a1-1)
        
    if dfs(a):ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
def is_linking(sides):
    side = copy.copy(sides.pop())
    flag = True
    while flag:
        if not sides:
            if len(side) == n:
                return True
            else:
                return False
        for i in range(len(sides)):
            if side & sides[i]:
                side |= sides.pop(i)
                break
            elif i == len(sides) - 1:
                flag = False
    if len(side) == n:
        return True
    else:
        return False       
    
n, m = map(int, input().split())
all_sides = [set(input().split()) for _ in range(m)]
count = 0
for i in range(m):
    sides = all_sides[:i] + all_sides[i+1:]
    if is_linking(sides):
        continue
    else:
        count += 1
print(count)