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:
# よくわからんが隣接リストのDFSで間に合うのでは

n, m = map(int, input().split())
gets = []  # とっておく
for _ in range(m):
    s, t = map(int, input().split())
    gets.append([s-1, t-1])
ans = 0
for i in range(m):
    graph = [[] for _ in range(n)]  # 隣接リスト
    for j in range(m):
        # 採用しない橋以外を採用する
        if i != j:
            s, t = gets[j]
            graph[s].append(t)
            graph[t].append(s)
    stack = [0]
    visited = [False for _ in range(n)]
    # 適当に0から始めて伸ばす
    visited[0] = True
    while len(stack):
        nex = stack.pop()
        for g in graph[nex]:
            if visited[g] == False:
                visited[g] = True
                stack.append(g)
    count = list(filter(lambda x: x == True, visited))
    ans += 1 if n-len(count) > 0 else 0

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def bfs(a,b):
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        q = deque()
        q.append(0)
        s = 1
        while q:
            x = q.pop()
            for y in v[x]:
                if [x,y] != [a,b] and [x,y] != [b,a]:
                    if bfs_map[y]:
                        bfs_map[y] = 0
                        q.append(y)
                        s += 1
        return s
    n,m = LI()
    v = [deque() for i in range(n)]
    l = deque()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        l.append([a,b])
    ans = 0
    for a,b in l:
        s = bfs(a,b)
        if s < n:
            ans += 1
    print(ans)
#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self._tree = [i for i in range(n)]
        self._rank = [1] * n
    def root(self, a):
        if self._tree[a] == a:return a
        self._tree[a] = self.root(self._tree[a])
        return self._tree[a]
    def is_same_set(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._rank[ra] < self._rank[rb]:
            self._tree[ra] = rb
        else:
            self._tree[rb] = ra
            if self._rank[ra] == self._rank[rb]:
                self._rank[ra] += 1
I=lambda:map(int,input().split())
N,M=I()
edges=[list(I()) for _ in range(M)]
r=0
for i in range(M):
  uf=UnionFind(N)
  for j in range(M):
    if j!=i: uf.unite(edges[j][0]-1, edges[j][1]-1)
  s={uf.root(n) for n in range(N)}
  if len(s)>1:r+=1
print(r)

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

    def __root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.__root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def size(self, a):
        return self.__size[self.__root(a)]

    def groups(self):
        groups = {}
        for k in self.__parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    E = [tuple(map(int, input().split())) for _ in range(M)]
    ans = 0
    for i in range(M):
        uft = UnionFindTree(list(range(1, N+1)))
        for j in range(M):
            if i == j:
                continue
            a, b = E[j]
            uft.unite(a, b)
        if uft.size(1) != N:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

v = list(range(1,N+1))
edges = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int,input().split())
  edges[a] += [b]
  edges[b] += [a]

def dfs(v, e):
  for x in v:
    if(len(e[x]) == 1):
      t = e[x][0]
      e[x] = []
      e[t].remove(x)
      v.remove(x)
      return dfs(v, e)+1
  return 0

print(dfs(v, edges))

Submission status: Accepted

Solution code:
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

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

a = [list(map(int,input().split())) for i in range(m)]
co = 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])
    aa = list(uf.grouper())
    if len(aa) != 2:
        co +=1
print(co)

Submission status: Accepted

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

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

for i in range(m) :
    B[A[i][0]].append(A[i][1])
    B[A[i][1]].append(A[i][0])

co = 0
ok = 0
while ok == 0 :
    ok = 1
    for i in range(1,n+1) :
        if len(B[i]) == 1 :
            ok = 0
            k = B[i][0]
            B[i].remove(k)
            B[k].remove(i)
            co += 1

print(co)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    self.n   = num
    self.size = [1]*num

#親を探す
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x]) #自分じゃなきゃ親を探す
      return self.par[x]

#集合を結合する(結合する前に親のポインタを取得する)
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] < self.rank[y]: #ランクの高い方に基準を合わせる
      x,y=y,x
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1
    self.par[y] = x
    self.size[x] += self.size[y]
    self.size[y] = 0

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

  def all_find(self):
    ls=[]
    for n in range(len(self.par)):
      ls.append(self.find(n))
    return ls


n,m=map(int,input().split())
uf=UnionFind(n)
ans=0
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append([a,b])
for i in range(m):
  uf=UnionFind(n)
  flag=False
  for j in range(m):
    a,b=ab[j]
    if i==j:
      continue
    uf.union(a-1,b-1)
  if len(set(uf.all_find()))>1:
    ans+=1
  # for j in range(n):
  #   for k in range(j,n):
  #     if not uf.same(j,k):
  #       flag=True
  # if flag:
  #   ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    self.n   = num
    self.size = [1]*num

#親を探す
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x]) #自分じゃなきゃ親を探す
      return self.par[x]

#集合を結合する(結合する前に親のポインタを取得する)
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] < self.rank[y]: #ランクの高い方に基準を合わせる
      x,y=y,x
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1
    self.par[y] = x
    self.size[x] += self.size[y]
    self.size[y] = 0

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

  def all_find(self):
    for n in range(len(self.par)):
      self.find(n)


n,m=map(int,input().split())
uf=UnionFind(n)
ans=0
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append([a,b])
for i in range(m):
  uf=UnionFind(n)
  flag=False
  for j in range(m):
    a,b=ab[j]
    if i==j:
      continue
    uf.union(a-1,b-1)
  for j in range(n):
    for k in range(j,n):
      if not uf.same(j,k):
        flag=True
  if flag:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    self.n   = num
    self.size = [1]*num

#親を探す
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x]) #自分じゃなきゃ親を探す
      return self.par[x]

#集合を結合する(結合する前に親のポインタを取得する)
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] < self.rank[y]: #ランクの高い方に基準を合わせる
      x,y=y,x
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1
    self.par[y] = x
    self.size[x] += self.size[y]
    self.size[y] = 0

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

  def all_find(self):
    for n in range(len(self.par)):
      self.find(n)


n,m=map(int,input().split())
uf=UnionFind(n)
ans=0
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append([a,b])
for i in range(m):
  uf=UnionFind(n)
  flag=False
  for j in range(m):
    a,b=ab[j]
    if i==j:
      continue
    uf.union(a-1,b-1)
  for j in range(n):
    for k in range(j,n):
      if not uf.same(j,k):
        flag=True
  if flag:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    self.n   = num
    self.size = [1]*num

#親を探す
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x]) #自分じゃなきゃ親を探す
      return self.par[x]

#集合を結合する(結合する前に親のポインタを取得する)
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] < self.rank[y]: #ランクの高い方に基準を合わせる
      x,y=y,x
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1
    self.par[y] = x
    self.size[x] += self.size[y]
    self.size[y] = 0

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

  def all_find(self):
    for n in range(len(self.par)):
      self.find(n)


n,m=map(int,input().split())
# edges=[[0]*n for i in range(n)]
# uf=UnionFind(n)
ans=0
# ab=[]
# for i in range(m):
#   a,b=map(int,input().split())
#   ab.append([a,b])
#   uf.union(a-1,b-1)
# for i in range(m):
#   uf1=UnionFind(n)
#   for j in range(m):
#     a,b=ab[j]
#     if i==j:
#       continue
#     uf1.union(a-1,b-1)
#   if all([True if i==j else False for i,j in zip(uf.par,uf1.par)])!=True:
#     ans+=1
nl=[]
for i in range(m):
    f,t=map(int,input().split())
    nl.append([f-1,t-1])
for i in range(m):
    uf=UnionFind(n)
    flag=False
    for j in range(m):
        if i==j:
            continue
        uf.union(nl[j][0],nl[j][1])
    nl.append(t)
    for j in range(n):
        for k in range(n):
            if not uf.same(j,k):
                flag=True
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# UnionFind構造

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]

count = 0
for i in range(len(lst)):
    llst = lst[:]
    del llst[i]
    a = UnionFind(n)
    for i in llst:
        a.union(i[0], i[1])
    rootset = set()
    for i in range(1, n+1):
        rootset.add(a.find(i))
    if len(rootset)==1:
        pass
    else:
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
import copy

n,m=map(int,input().split())
l=[]
for i in range(m):
    x,y=map(int,input().split())
    l.append([x,y])

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[0]*(n)
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):
        return self.find(x)==self.find(y)
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

ans=0
for i in range(m):
    uf=UnionFind(n)
    x=copy.deepcopy(l)
    x.pop(i)
    for a,b in x:
        uf.union(a-1,b-1)
    y=l[i][0]-1
    z=l[i][1]-1
    if uf.same_check(y,z):
        ans+=1

print(m-ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
	p, l = map(int, input().split(" "))
	
	lines = []
	for i in range(l):
		a, b = map(int, input().split(" "))
		a, b = a - 1, b - 1
		lines.append((a, b))
		
	result = 0
	for i, val in enumerate(lines):
		uf = UnionFind(p)
		for i, val2 in enumerate(lines):
			if val == val2:
				continue
			a, b = val2
			uf.union(a, b)
			
		aa, _ = lines[0]
		for i in range(p):
			if uf.is_same(aa, i) == False:
				result = result + 1
				break
				
	print(result)

class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import copy
N,M=map(int,input().split())
A=[[] for n in range(N)]
I=[]
for m in range(M):
	I.append(list(map(int,input().split())))
	I[m][0]-=1
	I[m][1]-=1
	A[I[m][0]].append(I[m][1])
	A[I[m][1]].append(I[m][0])

def check(n):
	global C,AA
	if C[n]==1:
		return
	else:
		C[n]=1	
		for nn in AA[n]:
			check(nn)
		return
ans=M
for i in I:
	C=[0 for n in range(N)]
	AA=copy.deepcopy(A)
	AA[i[0]].remove(i[1])
	AA[i[1]].remove(i[0])
	check(0)
	ans-=all(C)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy as dc

N, M = map(int, input().split())
edges = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(M)]

edges_map = [[False for _ in range(N)] for _ in range(N)]
for edge in edges:
    edges_map[edge[0]][edge[1]] = True
    edges_map[edge[1]][edge[0]] = True
visited = [False for _ in range(N)]

def dfs(edge_now, edges_map, visited):
    visited[edge_now] = True
    for edge_to in range(N):
        if visited[edge_to]:
            continue
        if not edges_map[edge_now][edge_to]:
            continue
        dfs(edge_to, edges_map, visited)

def is_true(visited):
    if False in visited:
        return 1
    return 0

ans = 0
for edge in edges:
    visited_lc = dc(visited)
    edges_map_lc = dc(edges_map)
    edges_map_lc[edge[0]][edge[1]] = False
    edges_map_lc[edge[1]][edge[0]] = False
    dfs(0, edges_map_lc, visited_lc)
    ans += is_true(visited_lc)

print(ans)

Submission status: Accepted

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


data = [-1]*(N+1)
rank = [1]*(N+1)
con  = [1] * (N+1)
def find(a):
    while data[a] != -1:
        a = data[a]
    return a
def unite(a,b):
    a=find(a); b=find(b)
    if a != b:
        if rank[a] < rank[b]:
            b,a = a,b
        if rank[a] == rank[b]:
            rank[a] += 1
        rank[b] += rank[a]
        data[b] =  a
        con[a]  += con[b]


con = [ [] for _ in range(N+1)]

def is_edge(a):
    if len(con[a]) == 1:
        return True
    return False


conF = [ [False] * (N+1) for _ in range(N+1)]
for a,b in AB:
    # if find(a) != find(b):
    #     ans += 1
    #     unite(a,b)
    con[a].append(b)
    con[b].append(a)
    conF[a][b] = True
    conF[b][a] = True

def dfs(cnt, n, par,  target, visited):
    # print("dfs({}, {}, {}, {}, {}".format(cnt, n, par, target, visited))
    if cnt != 0 and n == target:
        return True

    found = False
    visited[n] = True
    for ch in con[n]:
        if ch == par: continue
        if visited[ch]: continue
        if not conF[ch][n] : continue

        found = dfs(cnt+1, ch, n, target, visited[:])
        if found:
            # print("\tFound!")
            break
    if found:
        return True
    else:
        return False

ans = 0
for a,b in AB:
    conF[a][b] = False
    conF[b][a] = False

    found = False
    for ch in con[a]:
        if ch == b: continue
        visited = [False] * (N+1)
        visited[a] = True
        
        found = dfs(0, ch ,a, b, visited[:])
        if found:
            break
    if not found:
        # print("a: ", a, "b: ", b, "+1! ")
        ans += 1
    # ---- 
    conF[a][b] = True
    conF[b][a] = True

print(ans)

Submission status: Accepted

Solution code:
class Unionfind:

    __slots__ = ['nodes']

    def __init__(self, n):
        self.nodes = [-1]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        rank_x = -self.nodes[x]; rank_y = -self.nodes[y]
        if rank_x < rank_y:
            x, y = y, x
        if rank_x == rank_y:
            self.nodes[x] -= 1
        self.nodes[y] = x

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

    def rank(self, x):
        return -self.nodes[self.root(x)]

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

def bridge(k):
    uf = Unionfind(N)
    for i,pair in enumerate(info):
        if i == k: continue
        a = pair[0] - 1; b = pair[1] - 1
        uf.unite(a,b)
    s = {uf.root(i) for i in range(N)}
    if len(s) != 1:
        return True
    return False

cnt = 0
for k in range(M):
    if bridge(k):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict


def f(edges, start):
    mp = defaultdict(lambda: [])
    for a, b in edges:
        mp[a].append(b)
        mp[b].append(a)

    res = {start}
    q = [start]

    while True:
        if len(q) == 0:
            return res
        i = q.pop()
        nei = mp[i]
        for j in nei:
            if j in res:
                continue
            res.add(j)
            q.append(j)
    return res


def check(n, edges, start):
    a = f(edges, start)
    return len(a) != n


def main():
    n, m = [int(a) for a in input().split()]
    ab = [
        [int(a) - 1 for a in input().split()]
        for _ in range(m)
    ]

    c = 0
    for i in range(m):
        if check(n, ab[:i] + ab[i + 1:], ab[i][0]):
            c += 1
    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
def find(x,par):
  if par[x] == x:
    return x
  else:
    return find(par[x],par)
def unite(x,y,par,rank):
  x = find(x,par)
  y = find(y,par)
  if x != y:
    if rank[x] < rank[y]:
      par[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
def same(x,y,par):
  return find(x,par) == find(y,par)
cnt = 0
for i in range(M):
  par = []
  rank = [0]*N
  for j in range(N):
    par.append(j)
  TF = [True]*M
  TF[i] = False
  for k in range(M):
    if TF[k] == True:
      unite(L[k][0]-1,L[k][1]-1,par,rank)
  flag = True
  for l in range(N):
    for m in range(N):
      if not same(l,m,par):
        flag = False
  if flag:
    cnt += 1
print(M-cnt)

Submission status: Accepted

Solution code:
import copy
N,M=map(int,input().split())
 
A = [[int(i)-1 for i in input().split()] for i in range(M)]
#print(A)
def dfs(x):
  if visited[x]:
    return
  visited[x]=True
  for i in range(N):
    if edgemat[x][i]:
      dfs(i)
answer=0
 
for i in range(M):
  visited=[False]*N
  Acopy=copy.deepcopy(A)
  del Acopy[i]
  edgemat=[[0] *N for j in range(N)]
  for m,n in Acopy:
    edgemat[m][n]=1
    edgemat[n][m]=1
  dfs(0)
  if any(visited[y] == False for y in range(N)):
    answer+=1
print(answer)

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self, N):
        self.N = N
        self.par = [i for i in range(N)]
        self.height = [0 for i in range(N)]
    def Find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.Find(self.par[x])
        return self.par[x]
    def Union(self, x, y):
        x, y = self.Find(x), self.Find(y)
        if self.height[x] < self.height[y]:
            self.par[x] = y
        else:
            self.par[y] = self.par[x]
            if self.height[x] == self.height[x]:
                self.height[x] += 1
    def Same(self, x, y):
        return Find(x) == Find(y)

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    uf = Union_Find(N)
    for j in range(M):
        if i == j:
            continue
        uf.Union(edges[j][0] - 1, edges[j][1] - 1)
    cnt = 0
    for i in range(N):
        if uf.par[i] == i:
            cnt += 1
    if cnt > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(i,edge):
    if vis[i]==True:
        return
    vis[i]=True
    for j in edge[i]:
        dfs(j,edge)

N,M=map(int,input().split())
ab=[[0,0] for _ in range(M)]
for i in range(M):
    a,b=map(int,input().split())
    ab[i][0],ab[i][1]=a,b
ans=0
for i in range(M):
    edge=[[] for _ in range(N+1)]
    for j in range(M):
        if j!=i:
            edge[ab[j][0]].append(ab[j][1])
            edge[ab[j][1]].append(ab[j][0])
    vis=[False]*(N+1)
    vis[0]=True
    dfs(1,edge)
    if False in vis:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

N, M = map(int, input().split())
N += 1
A = [[int(i) for i in input().split()] for i in range(M)]
    
def dfs(x):
    if vis[x]:
        return
    vis[x] = True
    for  i in range(N):
        if G[x][i]:
            dfs(i)
            
cnt = 0
for i in range(M):
    vis = [False] * N
    A2 = copy.deepcopy(A)
    del A2[i]
    G = [[0] * N for i in range(N)]
    for i, j in A2:
        G[i][j] = 1
        G[j][i] = 1
        
    dfs(1)
    if any(vis[i] == False for i in range(1, N)):
        cnt += 1
        
print(cnt)

Submission status: Accepted

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

def BFS(i,E,V):
    if all(V):
        return True
    if V[i]:
        return False
    V[i]=True
    if any([BFS(v,E,V) for v in E[i]]):
        return True
    return False

n,m=map(int,input().split())
Edges=[list(map(int,input().split())) for _ in range(m)]
ans=0
for i in range(m):
    E_i=[[] for _ in range(n)]
    for j in range(m):
        if i!=j:
            E_i[Edges[j][0]-1].append(Edges[j][1]-1)
            E_i[Edges[j][1]-1].append(Edges[j][0]-1)
    Visited=[False]*n
    if not BFS(0,E_i,Visited):
        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 bfs(i, edges, r):
    if all(r):
        return True
    if r[i]:
        return False
    r[i] = True
    if any([bfs(e, edges, r) for e in edges[i]]):
        return True
    return False

ans = 0
for i in range(m):
    edges = [[] for _ in range(n)]
    for j in range(m):
        if i != j:
            edges[ab[j][0]-1].append(ab[j][1]-1)
            edges[ab[j][1]-1].append(ab[j][0]-1)
    reached = [False for _ in range(n)]
    if not bfs(0, edges, reached):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def c_bridge(N, M, E):
    # N: 頂点の数, M: 辺の数, E: 辺で結ばれる頂点の組
    def dfs(v):
        is_visited[v] = True  # 現在の頂点を訪問済にする
        for v2 in range(N):
            if not graph[v][v2] or is_visited[v2]:
                continue  # 頂点v2に行けないか、行く必要がない
            dfs(v2)

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

    # 各辺は橋か？ グラフからその辺を取り除いて、グラフが連結かを判定
    ans = 0
    for a, b in E:
        # 辺を取り除く
        graph[a - 1][b - 1] = False
        graph[b - 1][a - 1] = False

        # すべての辺を未訪問として初期化
        is_visited = [False for _ in range(N)]
        # 頂点0からDFS
        dfs(0)
        # すべての頂点が訪問済なら連結、そうでなければ非連結
        if not all(is_visited):
            ans += 1

        # 辺を復元
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(c_bridge(N, M, E))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        """
        size:頂点の数
        """
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        """
        xのrootを返す
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        x,yを同じグループとしてまとめる
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        """
        xとyが同じグループならTrue
        """
        return self.find(x) == self.find(y)

    def component(self):
        """
        各連結成分のrootの集合を返す
        len()をとれば連結成分の数が求められる
        return-> set()
        """
        comp = set()
        for i in self.parent:
            p = self.find(i)
            comp.add(p)
        return comp

    def __str__(self):
        """
        for debug
        クラスのlistの情報を出力
        """
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


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

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

ans = 0
for e in edges:
    Un = UnionFind(N)
    for g in edges:
        if e == g:
            continue
        else:
            Un.union(g[0], g[1])
    if not Un.same(e[0], e[1]):
        ans += 1
print(ans)