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 Counter

n , m = map(int, input().split())
err = 0
ans = 0

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

ans = 0
for i in range(m):
    for v in range(n):
        par[v] = v
        rank[v] = 0
        
    for j in range(m):
        if j == i:
            continue
        unite(a[j]-1 , b[j]-1)
        r = [find(k) for k in range(n)]
    if len(Counter(r)) != 1:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
class Unionfind():

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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.par[x]>self.par[y]:
            x,y = y,x
        self.par[x]+=self.par[y]
        self.par[y] = x
        return True

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

    def count_group():
        c = 0
        for i in range(len(self.par)):
            if self.par[i]<0:
                c+=1
        return c

n,m = map(int, input().split())
a = []
for i in range(m):
    b = list(map(int, input().split()))
    b[0]-=1
    b[1]-=1
    a.append(b)
ans = 0
for i in range(m):
    uf = Unionfind(n)
    for j in range(m):
        if i==j:
            continue
        uf.union(a[j][0],a[j][1])
    if uf.same(a[i][0],a[i][1]):
        continue
    else:
        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 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())
L = [[] for i in range(M)]
for i in range(M):
  L[i]=list(map(int,input().split()))

def chk(LL):
  uf = UnionFind(N)
  for l in LL:
    uf.union(l[0]-1, l[1]-1)
  return uf.group_count()

ret = 0
for i in range(M):
  LL = L[:]
  LL.pop(i)
  if chk(LL)>1:
    ret+=1
print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import sys
sys.setrecursionlimit(10**8)

def main():
  n, m = map(int, input().split())
  tree = [[] for _ in range(n)]
  for im in range(m):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
  
  def get_bridge(tree):
    bridge_targets = []
    n = len(tree)
    pres = [0 for _ in range(n)]
    lows = [0 for _ in range(n)]
    visited = [0 for _ in range(n)]
    used_edges = []
    def dfs(inode, count=0):
      pres[inode] = lows[inode] = count
      visited[inode] = 1
      for ichild in tree[inode]:
        if not visited[ichild]:
          used_edges.append((inode, ichild))
          count = dfs(ichild, count+1)
        if lows[ichild] < lows[inode]:
          if not (ichild, inode) in used_edges:
            lows[inode] = lows[ichild]
      if pres[inode] == lows[inode]:
        bridge_targets.append(inode)
      
      return count
    dfs(0)
    return [(s, t) for (s, t) in used_edges if t in bridge_targets]
  bridges = get_bridge(tree)
  print(len(bridges))
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n , m = map(int, input().split())
combis = [set(list(map(int, input().split()))) for i in range(m)]
count = 0
for i in range(m):
    combis_x = combis[0:i] + combis[i+1:m]
    islands = []
    for combi in combis_x:
        # init
        if not islands:
            islands.append(combi)
            continue
        # compare existed islands
        new_islands = islands
        joint_i = []
        for j, island in enumerate(islands):
            if not island.isdisjoint(combi):
                new_islands[j] = island | combi
                joint_i.append(j)
        else:
            if not joint_i:
                new_islands.append(combi)
            elif len(joint_i) == 2:
                new_islands[joint_i[0]] = new_islands[joint_i[0]] | new_islands[joint_i[1]]
                new_islands.pop(joint_i[1])
        islands = new_islands

    # judge
    if len(islands) == 1 and len(islands[0]) == n:
        continue
    elif len(islands) == 1 and len(islands[0]) == n - 1:
        count += 1
    else:# len(islands) == 2 and islands[0].isdisjoint(islands[1]):
        count += 1
print(count)

Submission status: Accepted

Solution code:
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]
  
n, m = map(int, input().split())
links = [set() for _ in range(n)]
 
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
 
ans = 0
pre = [-1] * n
low = [-1] * n
dfs(0, 0, None)
print(ans - 1)
'''
まず、頂点を１つ選び、DFSを開始する。
各頂点には、pre、lowという２つのデータを記録する。
preは、DFS木の行きがけ順（pre-order）の値を保持する。
lowは、DFS木でその頂点から到達しうる頂点のpreの最小値を保持する。
初期値はその頂点のpreである。
次の頂点が、すでに訪れてある（preの値が存在する）場合は、
自分のlowを、次の頂点のlowと比べて小さい方に更新する。
次の頂点をまだ訪れていない場合は、その頂点に対してDFSを続ける。
そして、その頂点へのDFSが終了した際に、lowがpreより小さくなっていれば、
その頂点へ向かう辺は橋である。
'''

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                # 根でないなら親の要素で再検索
                data.append(now)
                queue.append(self.par[now])
        # 検索する過程で親を更新
        for y in data:
            self.par[y] = root
        return root

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

    # 同じ集合に属しているか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def size(self, x):
        q = UnionFind.find(self, x)
        return self.count[q]


n, m = map(int, input().split())
data = [tuple(map(lambda z: int(z) - 1, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    u = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        u.union(data[j][0], data[j][1])
    ans += 0 if u.same_check(data[i][0], data[i][1]) else 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import queue

N,M=map(int,input().split())
ab=[]
d=defaultdict(list)
for i in range(M):
    a,b=map(int,input().split())
    ab.append((a,b))
    d[a].append(b)
    d[b].append(a)


ans=0
for i in range(M):
    Remove=ab[i]
    d[Remove[0]].remove(Remove[1])
    d[Remove[1]].remove(Remove[0])
    
    dist=[False]*N
    q=queue.Queue()
    q.put(list(d.keys())[0])

    while not q.empty():
        From=q.get()
        dist[From-1]=True
        for g in d[From]:
            if dist[g-1]==False:
                q.put(g)
    
    if False in dist:
        ans+=1

    d[Remove[0]].append(Remove[1])
    d[Remove[1]].append(Remove[0])

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -1

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

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

	def Max_tree(self):
		return min(self.root) * (-1)

n, m = map(int, input().split())
AB = np.array(sys.stdin.read().split(), np.int64)
A = AB[::2]
B = AB[1::2]

ans = 0
for i in range(m):
	solve = UnionFind(n+1)
	for j in range(m):
		if j == i:
			continue
		
		solve.Unite(A[j],B[j])

	if solve.Max_tree() != n:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys 

N, M = map(int, input().split())
AB = np.array(sys.stdin.read().split(), np.int64)
A = AB[::2]
B = AB[1::2]
E = np.zeros([N+1, N+1], np.int64)

np.add.at(E,(A,B),1)
np.add.at(E,(B,A),1)

def dfs(E):
	flg = np.zeros(1+N)
	flg[0] = 0
	q = [1]

	while q:
		cp = q.pop()
		flg[cp] = 1

		for n in range(1,N+1):
			if flg[n] == 0 and E[cp][n] == 1:
				flg[n] = 1
				q.append(n)

	if flg.sum() == N:
		return 0
	else:
		return 1

ans = 0
for i in range(1,N+1):
	for j in range(i+1,N+1):
		if E[i,j] == 0:
			continue

		E[i,j] = 0
		E[j,i] = 0

		ans += dfs(E)

		E[i,j] = 1
		E[j,i] = 1

print(ans)

Submission status: Accepted

Solution code:
import math
import bisect
import heapq
from collections import deque

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

p = [[0] * n for _ in range(n)]

c, d = [0] * m, [0] * m
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    c[i],d[i] = a,b

    p[a][b], p[b][a] = 1, 1


def dfs(p):
    seen = [False] * n
    s = 0
    deq = deque([0])
    while deq:
        s = deq.pop()
        seen[s] = True
        for i in range(n):
            if p[s][i] == 0 or seen[i]:
                continue
            deq.append(i)

    for i in range(n):
        if not seen[i]:
            return 1
    return 0


ans = 0

for i in range(m):
    a,b = c[i],d[i]
    p[a][b], p[b][a] = 0, 0

    ans += dfs(p)
    p[a][b], p[b][a] = 1, 1

print(ans)

Submission status: Accepted

Solution code:
import math
import bisect
import heapq
from collections import deque

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

p = [[0] * n for _ in range(n)]

c, d = [0] * m, [0] * m
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    c[i],d[i] = a,b

    p[a][b], p[b][a] = 1, 1


def dfs(p,n):
    seen = [False] * n
    s = 0
    deq = deque([0])
    while deq:
        s = deq.pop()
        seen[s] = True
        for i in range(n):
            if p[s][i] == 0 or seen[i]:
                continue
            deq.append(i)

    for i in range(n):
        if not seen[i]:
            return 1
    return 0


ans = 0

for i in range(m):
    a,b = c[i],d[i]
    p[a][b], p[b][a] = 0, 0

    ans += dfs(p,n)
    p[a][b], p[b][a] = 1, 1

print(ans)

Submission status: Accepted

Solution code:
def find(x):
    if x != T[x][0]:
        while x!=T[x][0]:
            x = T[x][0]
    return x
def union(x,y):
    rt0 = find(x)
    rt1 = find(y)
    if T[rt0][1]>T[rt1][1]:
        T[rt1][0] = rt0
    elif T[rt0][1]==T[rt1][1]:
        T[rt1][0] = rt0
        T[rt0][1] += 1
    else:
        T[rt0][0] = rt1
        
N,M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
B = []
for j in range(M):
    T = {i:[i,0] for i in range(1,N+1)}
    for i in range(M):
        if i==j:continue
        a,b = A[i]
        union(a,b)
    R = [0 for _ in range(N+1)]
    for k in range(1,N+1):
        rt = find(k)
        if R[rt]==0:
            R[rt]=1
    if sum(R)>1:
        B.append(j)
print(len(B))

Submission status: Accepted

Solution code:
# 1-index
from sys import stdin
N, M = [int(x) for x in stdin.readline().rstrip().split()]
adj_matrix = [[0]*(N+2) for i in range(N+2)]

edges = []

for i in range(M):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    edges.append((a, b))
    adj_matrix[a][b] = 1
    adj_matrix[b][a] = 1

def dfs(i):
    if is_visited[i]:
        return False

    is_visited[i] = True

    for node,bi in enumerate(adj_matrix[i][:-1]):
        if bi == 1:
            dfs(node)

ans = 0
for j, k in edges:
    is_visited = [False for i in range(N+1)]
    adj_matrix[j][k] = 0
    adj_matrix[k][j] = 0
    dfs(1)
    if not all(is_visited[1:]):
        ans += 1
    adj_matrix[j][k] = 1
    adj_matrix[k][j] = 1
        
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

n, m = map(int, input().split())
graph = [[] for i in range(n)]
arcs = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    arcs.append((a, b))
answer = 0
for a, b in arcs:
    graph_ = deepcopy(graph)
    graph_[a].remove(b)
    graph_[b].remove(a)

    initial = 0
    stack = []
    history = set()
    stack.append(initial)
    history.add(initial)

    while stack:
        node = stack.pop()
        for new_node in graph_[node]:
            if new_node not in history:
                stack.append(new_node)
                history.add(new_node)
    
    if len(history) != n:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

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

d = [0] + [-1]*(N-1)

def dfs(n):
    d[n] = 0
    for v in G[n]:
        if d[v] == -1:
            dfs(v)

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

    dfs(0)

    if -1 in d:
        ans += 1
    
    for i in range(1,N):
        d[i] = -1
    G[a].append(b)
    G[b].append(a)

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(M) :
    a, b = edge[i]
    G[a][b] = G[b][a] = 0
    visited = [0]*N
    stuck = [0]
    while stuck :
        next = stuck.pop()
        visited[next] = 1
        for i in range(N) :
            if G[next][i] == 1 :
                if visited[i] == 1 :
                    continue
                if i in stuck :
                    continue
                stuck.append(i)
    G[a][b] = G[b][a] = 1
    if 0 in visited :
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x): # 根を探す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N,M=MAP()
    
    edges = []
    for _ in range(M):
        a,b = MAP()
        edges.append((a-1,b-1))

    answer = 0
    for i in range(M): # i番目の辺を使わない
        uf = UnionFind(N)

        for j in range(M):
            if i == j:
                continue

            a,b = edges[j]
            uf.union(a,b)
        if uf.group_count() > 1:
            answer += 1
    print(answer)
    return

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

n, m = map(int, input().split())
edge = []
for i in range(m):
    a, b = map(int, input().split())
    edge.append([a - 1, b - 1])
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j: uf.unite(edge[j][0], edge[j][1])
    ans += not uf.same(edge[i][0], edge[i][1])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
####not yet
def DFS_Stack_matrix(matrix,start): #隣接行列のDFS
    list_nodes = [start]
    n = len(matrix[0])
    stac = deque()
    flag = False
    while len(list_nodes) <  n :#start以外全部訪れたらおわり
        for i in range(n):
            if matrix[start][i] == 1:
                stac.append(i)  #startに隣接する要素を追加
        while stac:# if stac is not emnpty
            start = stac.pop() # stac から次に訪問するノードを取り出す
            if start in list_nodes:
                continue#訪問済みなら新しいstartを探す
            else:
                list_nodes.append(start) #訪問済みリストに追加
                break
        else:
            break
    else:
        flag = True
    return flag


n,m = map(int,input().split())
mat = [[0]*n for i in range(n)]
ind = []
for i in range(m):
    u,v = map(int,input().split())
    mat[u-1][v-1] =1
    mat[v-1][u-1] = 1
    ind.append([u,v])

cnt = 0
for u,v in ind:
    mat[u-1][v-1] = 0
    mat[v-1][u-1] = 0
    if DFS_Stack_matrix(mat,0):
        pass
    else:
        cnt +=1
    mat[u-1][v-1] = 1
    mat[v-1][u-1] = 1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# from collections import Counter

parent = None


def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]


def is_same(a, b):
    return root(a) == root(b)


def unite(a, b):
    # print('before:',end='')
    # print(parent)
    ra = root(a)
    rb = root(b)
    # print(ra, rb, sep='|')
    if ra == rb:
        return
    parent[ra] = rb
# print('after:',end='')
# print(parent)


n, m = map(int, input().split())
grid = []

for i in range(m):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    grid.append((x, y))
    # grid[y][x] = 1

# print(grid)

ans = 0
for i in range(m):
    # print('-----------------------')
    parent = [k for k in range(n)]
    # print(parent)

    for j, e in enumerate(grid):
        # print(j, e, sep='#')
        if j == i:
            continue
        a, b = e
        unite(a, b)

    # print(grid[i], parent, sep='=')
    a, b = grid[i]
    if not is_same(a, b):
        # print(parent)
        ans += 1
    # print(parent)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
q = deque()
for i in range(m):
    a,b = v[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 deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        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
            stk.append((nxt,cur))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        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
            stk.append((nxt,cur))

print(ans)

Submission status: Accepted

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

node_list = [[False]*n for i in range(n)]
graph = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    graph[i] = [a, b]
    node_list[a-1][b-1] = True
    node_list[b-1][a-1] = True

ans = m
for i in range(m):
    p, q = graph[i][0], graph[i][1]
    node_list[p-1][q-1] = False
    node_list[q-1][p-1] = False
    already = [False]*n
    not_yet = []
    already[0] = True
    for j in range(n):
        if node_list[0][j]:
            not_yet.append(j)
    while not_yet:
        k = not_yet[-1]
        not_yet.pop()
        already[k] = True
        for j in range(n):
            key = node_list[k][j]
            if key:
                if not already[j]:
                    not_yet.append(j)
    node_list[p-1][q-1] = True
    node_list[q-1][p-1] = True
    if all(already):
        ans -= 1
  
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())


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

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

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

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

node_list = []
for i in range(m):
    node_list.append([int(x) for x in input().split()])

ans = 0
for i in range(m):
    par = [-1 for _ in range(n)]
    for j in range(m):
        if i == j:
            continue
        else:
            union(node_list[j][0]-1, node_list[j][1]-1)
    limit = 2
    flag = False
    for value in par:
        if value < 0:
            limit -= 1
        if not limit:
            flag = True
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#abc075 c
n,m=map(int,input().split())
graph=[[0]*n for _ in range(n)]
visited=[0]*n
hen=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    hen.append([a,b])
    graph[a][b]=graph[b][a]=1

def dfs(x):
    if visited[x]==1:
        return 0
    visited[x]=1
    for i in range(n):
        if graph[x][i]:#xとiがつながっているとき
            dfs(i)#graph[x][i]は0か1で頂点ではない


ans=0
for i in range(m):
    a,b=hen[i]
    graph[a][b]=graph[b][a]=0#ab間の辺を消す
    visited=[0]*n#visitedを初期化
    dfs(0)
    bridge=False
    for j in range(n):
        if visited[j]==0:#訪れてない場所があるとき渡れない場所（複数頂点含む）
            bridge=True#端ができている
    if bridge:
        ans+=1
    graph[a][b]=graph[b][a]=1#ab間の辺を戻す

print(ans)

Submission status: Accepted

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n #各頂点への距離
    used=[False]*n
    d[s]=0
    
    while True:
        v=-1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1): #その頂点が使われたかチェック
                v=i			            #まだなら仮確定
            elif (not used[i]) and d[i]<d[v]: #より距離が近いのがあればそちらから
                v=i
        if v==-1:
             break
        used[v]=True
               
        for j in range(n):
            d[j]=min(d[j],d[v]+cost[v][j])
    return d
    
n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(m)]
now=0
ans=m
for _ in range(m):
    flag=True
    cost=[[10**9 for i in range(n)]for i in range(n)]
    for i in range(m):
        if i!=now:
            cost[a[i][0]-1][a[i][1]-1]=1
            cost[a[i][1]-1][a[i][0]-1]=1
    for j in dijkstra(0,n,m-1,cost):
        if j>100:
            flag=False
    if flag==True:
        ans-=1
    now+=1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n #各要素の親要素の番号を格納するリスト

    def find(self, x): #要素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が属するグループと要素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): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self,x,y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x)==self.find(y)

    def members(self,x): #要素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=[[int(i) for i in input().split()] for i in range(m)]
now=0
ans=0
for _ in range(m):
    uf=UnionFind(n)
    for ind,aa in enumerate(a):
        if ind!=now:
            uf.union(aa[0]-1,aa[1]-1)
    if uf.group_count()!=1:
        ans+=1
    now+=1
print(ans)