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して訪れられなかった場合に+1
n, m = map(int, input().split())
grpah = [[False for _ in range(n)] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    grpah[a - 1][b - 1] = True
    grpah[b - 1][a - 1] = True


def dfs(cur, visited):
    if all(visited) is False and all(grpah[cur]) is False:
        for i, v in enumerate(grpah[cur]):
            if v == True and visited[i] == False:
                visited[i] = True
                dfs(i, visited)


ans = 0

for i in range(n):
    for j in range(n):
        if grpah[i][j] or grpah[j][i]:
            # 辺を一時的に取り除く
            grpah[i][j] = grpah[j][i] = False
            temp_visited = [False for _ in range(n)]
            temp_visited[0] = True
            dfs(0, temp_visited)
            if all(temp_visited) is False:
                ans += 1

            # 取り除いた辺を復元しておく
            grpah[i][j] = grpah[j][i] = True

print(ans//2)

Submission status: Accepted

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

nodes = {}

for a, b in ab:
    if a in nodes:
        nodes[a].append(b)
    else:
        nodes[a] = [b]
    if b in nodes:
        nodes[b].append(a)
    else:
        nodes[b] = [a]

def dfs(s, nodes, visited):
    visited[s-1] = True
    q = []
    q.extend(nodes[s])
    
    while q:
        v = q.pop()
        if visited[v-1]:
            continue
        else:
            dfs(v, nodes, visited)
    
    return all(visited)

ans = 0

for a,b in ab:
    nodes[a].remove(b)
    nodes[b].remove(a)

    visited = [False for _ in range(N)]
    if not dfs(1,nodes,visited):
        ans += 1

    if a in nodes:
        nodes[a].append(b)
    else:
        nodes[a] = [b]
    if b in nodes:
        nodes[b].append(a)
    else:
        nodes[b] = [a]
    
print(ans)

Submission status: Accepted

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

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

ans = 0

for ab in abs:
    a = ab[0] - 1
    b = ab[1] - 1
    _abs = abs[::]
    _abs.remove(ab)

    dist_map = [[i == j for j in range(N)] for i in range(N)]

    for _ab in _abs:
        _a = _ab[0] - 1
        _b = _ab[1] - 1
        if not dist_map[_a][_b]:
            dist_map[_a][_b] = True
            dist_map[_b][_a] = True

    for i in range(N):
        for j in range(N):
            for k in range(N):
                dist_map[j][k] = dist_map[j][k] or (dist_map[j][i] and dist_map[i][k])
                dist_map[k][j] = dist_map[j][k]

    if not dist_map[a][b]:
        ans += 1

print(ans)

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)

    # 検索
    # 根ならその番号を返す
    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
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

g=[list(map(int,input().split())) for i in range(m)]


count=0
for i in range(m):
    uf=UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        if not uf.same_check(g[j][0], g[j][1]):
            uf.union(g[j][0], g[j][1])
    
    root=uf.find(1)
    for j in range(2,n+1):
        if not root==uf.find(j):
            count+=1
            break

print(count)

Submission status: Accepted

Solution code:
import copy

N,M=map(int,input().split())
l_2d = [[0] * N for i in range(N)]
edges=[]

def dfs(i):
    l_visit[i-1]=1
    for j in range(1,N+1):
        if l_2d_temp[i-1][j-1]==1 and l_visit[j-1]==0:
            dfs(j)
    return

for _ in range(M):
    i,j=map(int,input().split())
    edges.append([i,j])
    l_2d[i-1][j-1]=1
    l_2d[j-1][i-1]=1
    
ans=0
for edge in edges:
    i,j=edge
    l_2d_temp=copy.deepcopy(l_2d)
    l_2d_temp[i-1][j-1]=0
    l_2d_temp[j-1][i-1]=0

    l_visit=[0]*N

    dfs(1)
    if 0 in l_visit:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def check(graph,seen,now):
    seen[now] = True 
    for i in range(len(graph[now])):
        if seen[i] :
            continue
        if graph[now][i] == 0 :
            continue
        check(graph,seen,i)
    return seen


#入力
N,M = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(M)]
graph =[[0 for i in range(N)] for  j in range(N)]
for i in range(M):
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

#seen = [False]*(N)
ans = 0
for i in range(M):
    seen = [False]*(N)
    graph[para[i][0]-1][para[i][1]-1] = 0
    graph[para[i][1]-1][para[i][0]-1] = 0
    if False in check(graph,seen,0):
        ans += 1
    graph[para[i][0]-1][para[i][1]-1] = 1
    graph[para[i][1]-1][para[i][0]-1] = 1 

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
edges = defaultdict(dict)
pairs = []
for i in range(M):
    a, b = nl()
    pairs.append([a-1, b-1])
    edges[a-1][b-1] = True
    edges[b-1][a-1] = True

done = [False] * N

def check(v):
    done[v] = True
    for dst, on in edges[v].items():
        if not on or done[dst]:
            continue
        check(dst)

bridges = 0
for pair in pairs:
    edges[pair[0]][pair[1]] = False
    edges[pair[1]][pair[0]] = False

    done = [False] * N
    check(0)
    if not all(done):
        bridges += 1

    edges[pair[0]][pair[1]] = True
    edges[pair[1]][pair[0]] = True

print(bridges)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m=map(int,input().split())
bridge=[list(map(int,input().split())) for _ in range(m)]
def dfs(v):
    for i in g[v]:
        if visited[i]==0:
            visited[i]=1
            dfs(i)
    return

cnt=0
for i in range(m):
    g=[[] for _ in range(n)]
    visited=[0 for i in range(n)]
    bridge_=bridge[:i]+bridge[i+1:]
    for i in range(m-1):
        g[bridge_[i][0]-1].append(bridge_[i][1]-1)
        g[bridge_[i][1]-1].append(bridge_[i][0]-1)
#    print(g)
    dfs(0)
    if 0 in visited:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:

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

  def find(self, x):
    if self.par[x] != 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 x == y:
      return False
    elif self.rank[x] < self.rank[y]:
      self.par[x] = y
      self.sizes[y] += self.sizes[x]
    elif self.rank[x] > self.rank[y]:
      self.par[y] = x
      self.sizes[x] += self.sizes[y]
    else:
      self.par[y] = x
      self.rank[x] += 1
      self.sizes[x] += self.sizes[y]
    return True

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

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


n, m = list(map(int, input().split()))
edge = []
for i in range(m):
  a, b = list(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:
      continue
    uf.union(edge[j][0], edge[j][1])
  ans += uf.union(edge[i][0], edge[i][1])
print(ans)

Submission status: Accepted

Solution code:
# 全部試す
# 1つあたりO(M)
# O(M^2) = 10^6くらい
from scipy.sparse.csgraph import dijkstra
N,M = map(int,input().split())
edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0]*(N+1) for _ in range(N+1)]
for a,b in edge:
  graph[a][b] = 1

answer = 0
INF = 10 ** 9
for a,b in edge:
  graph[a][b] = INF
  dist = dijkstra(graph, indices = a, directed = False)
  if dist[b] >= INF:
    answer += 1
  graph[a][b] = 1

print(answer)

Submission status: Accepted

Solution code:
def dfs(v):
    stack.append(v)
    while len(stack)!=0:
        x = stack.pop()
        vis.append(x)
        for i in range(n):
            if graph[x][i]==False:
                continue
            if i in vis:
                continue
            if i in stack:
                continue
            stack.append(i)
 
n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append([False]*n)
a=[]
b=[]
for i in range(m):
    aa,bb = map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
for i in range(m):
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

ans=0
for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False
    vis=[]
    stack=[]
    dfs(0)
    bridge=False
    if len(vis) < n:
        bridge=True
    if bridge:
        ans+=1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True
print(ans)

Submission status: Accepted

Solution code:
def dfs(v):
    stack = [v]
    vis = []
    while len(stack)!=0:
        x = stack.pop()
        vis.append(x)
        for i in range(n):
            if graph[x][i]==False:
                continue
            if i in vis:
                continue
            if i in stack:
                continue
            stack.append(i)
    return len(vis)
 
n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append([False]*n)
a=[]
b=[]
for i in range(m):
    aa,bb = map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
for i in range(m):
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True
ans=0
for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False
    len_vis = dfs(0)
    bridge=False
    if len_vis < n:
        bridge=True
    if bridge:
        ans+=1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True
print(ans)

Submission status: Accepted

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

n,m = map(int,input().split())
visited=[False]*n
graph = []
for i in range(n):
    graph.append([False]*n)
a=[]
b=[]
for i in range(m):
    aa,bb = map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
for i in range(m):
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True
ans = 0
for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False
    for j in range(n):
        visited[j]=False
    dfs(0)
    bridge=False
    for j in range(n):
        if visited[j]==False:
            bridge =True
    if bridge:
        ans += 1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True
print(ans)

Submission status: Accepted

Solution code:
# 全部試す
# 1つあたりO(M)
# O(M^2) = 10^6くらい
import numpy as np
from scipy.sparse.csgraph import dijkstra
N,M = map(int,input().split())
edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0]*(N+1) for _ in range(N+1)]
for a,b in edge:
  graph[a][b] = 1

answer = 0
for a,b in edge:
  graph[a][b] = np.inf
  dist = dijkstra(graph, indices = a, directed = False)
  if dist[b] == np.inf:
    answer += 1
  graph[a][b] = 1

print(answer)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
adj_matrix = [[False]*n for _ in range(n)]
a, b = [False]*m, [False]*m

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

def dfs(v, used):
  used[v] = True
  
  if not False in used:
    return 1

  for i in range(n):
    if adj_matrix[v][i] is False:
      continue
    if used[i] is False:
      dfs(i, used)
  return 1
  
ans = 0

for i in range(m):
  adj_matrix[a[i]-1][b[i]-1] = False
  adj_matrix[b[i]-1][a[i]-1] = False
  used = [False]*n
  dfs(0, used)
  if False in used:
    ans += 1
  adj_matrix[a[i]-1][b[i]-1] = True
  adj_matrix[b[i]-1][a[i]-1] = True

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
e=[]
for i in range(M):
    a,b=map(int,input().split())
    #g[a-1].append(b-1)
    e.append([a-1,b-1])
#print('init g : ',g)
#print('e : ',e)

def dfs(G,v):
    #print('dfs start')
    #print('G,v : ',G,v)
    seen[v]=True
    #print('init seen : ',seen)
    for i in range(len(G[v])):
        if seen[G[v][i]]==True:
            #print('seen[',i,']==True')
            continue
        else:
            #print('call next')
            #print('G,G[v][i]',G,G[v][i])
            dfs(G,G[v][i])

cnt=0
for i in range(M):
    g=[[] for _ in range(N)]
    seen=[False for _ in range(N)]
    ee=e[:i]+e[i+1:]
    for j in range(M-1):
        a=ee[j][0]
        b=ee[j][1]
        g[a].append(b)
        g[b].append(a)
    #print('case : ',ee)
    #print('g : ',g)
    dfs(g,0)
    if False in seen:
        #print('cnt up')
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

def dfs(graph, start, goal):
    stack = deque()
    push, pop = stack.append, stack.pop
    push(start)
    visited = [False for i in range(N+1)]
    visited[start] = True
    
    while stack:
        a = pop()
        for b in graph[a].keys():
            if a in [start, goal] and b in [start, goal]:
                continue
            elif b == goal:
                return True
            elif not visited[b]:
                push(b)
                visited[b] = True
    return False

N,M = map(int, input().split())
graph = {}
bridge = []
for i in range(M):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
    bridge.append([a,b])

ans = 0
for a,b in bridge:
    ans += not dfs(graph, a, b)
print(ans)

Submission status: Accepted

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

graph = [[False for i in range(N+1)] for k in range(N+1)]

for tp in lis_s:
  graph[tp[0]][tp[1]] = True
  graph[tp[1]][tp[0]] = True


visited = [False]*(N+1)
bridge = False

def dfs(v):
  visited[v] = True
  for vs in range(1,N+1):
    if (graph[v][vs] == True) and (visited[vs] == False):
      dfs(vs)

ans = 0

for num in range(M):
  graph[lis_s[num][0]][lis_s[num][1]] = False
  graph[lis_s[num][1]][lis_s[num][0]] = False
  for i in range(N+1):
    visited[i] = False
  
  dfs(1)
  
  bridge = False
  for check in range(1,N+1):
    if visited[check] == False:
      bridge = True
  
  if bridge:
    ans += 1
  
  graph[lis_s[num][0]][lis_s[num][1]] = True 
  graph[lis_s[num][1]][lis_s[num][0]] = True
  
  
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[False] * N for _ in range(N)]
A = []
B = []
C = [False] * N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    G[a][b] = True
    G[b][a] = True


def dfs(v):
    C[v] = True
    for vv in range(N):
        if G[v][vv] is False:
            continue
        if C[vv] is True:
            continue
        dfs(vv)


def main():
    ans = 0
    for i in range(M):
        G[A[i]][B[i]] = False
        G[B[i]][A[i]] = False
        for j in range(N):
            C[j] = False
        dfs(0)
        G[A[i]][B[i]] = True
        G[B[i]][A[i]] = True
        if all(C) is False:
            ans += 1
            continue
    print(ans)


main()

Submission status: Accepted

Solution code:
n , m =  [ int(v) for v in input().split() ]
connect_matrix = [ [0 for j in range(n)] for i in range(n)]
breaking_list = []
for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_matrix[a][b] = 1
    connect_matrix[b][a] = 1
    breaking_list.append((a,b))




def connect_check(intuple):
    global connect_matrix,n
    p, q = intuple[0], intuple[1]

    connect_matrix2 = [ [connect_matrix[i][j] for j in range(n)] for i in range(n)]
    arriving_list =  [ set([i]) for i in range(n)]
    connect_matrix2[p][q] = 0
    connect_matrix2[q][p] = 0

    
    for k in range(6):
        new_connect_matrix2 = []
        for i in range(n):
            templist = [ j for j in range(n) if connect_matrix2[i][j] > 0 and j not in arriving_list[i]]

            newlist = [ connect_matrix2[i][j] for j in range(n) ]
            for j in templist:
                newlist = [ newlist[h] | connect_matrix2[j][h] for h in range(n) ]
                arriving_list[i].add(j)
            #print(newlist)
            new_connect_matrix2.append(newlist)
        connect_matrix2 = new_connect_matrix2


    
    if { i for i in range(n) } not in arriving_list:
        ret = 1
    else:
        ret = 0
    return ret

ans = 0
for i in breaking_list:
    ans += connect_check(i)

print(ans)

Submission status: Accepted

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])

C = []

for i in range(M):
    l = input().split()
    C.append([int(x) - 1 for x in l])

# print(N, M, C)

def visit(s, G, visited):
    # print(s, G, visited)
    visited.add(s)
    for g in G:
        if g[0] in visited:
            n = g[1]
            G.remove(g)
            return visit(n, G, visited)
        elif g[1] in visited:
            n = g[0]
            G.remove(g)
            return visit(n, G, visited)
    return

ans = 0
for i in range(M):
    D = []
    for j in range(M):
        if i != j:
            D.append(C[j])
    visited = set()
    visit(0, D, visited)
    # print(i, len(visited))
    if len(visited) != N:
        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 judge(ab,idx):
    memo = [True] * (N+1)
    al = [[] for _ in range(N+1)]
    for i in range(M):
        if i == idx:continue
        al[ab[i][0]].append(ab[i][1])
        al[ab[i][1]].append(ab[i][0])
            
    child = al[ab[idx][1]]
    memo[ab[idx][1]] = True
    while child:
        pi = child.pop()
        if memo[pi]:
            memo[pi] = False
        else:
            continue
        child = child + al[pi]
        
    if memo[ab[idx][0]] == True:
        return False
    else:
        return True
    
    
    
cnt = 0
for i in range(M):
    if not judge(ab,i):
        cnt += 1
        

print(cnt)

Submission status: Accepted

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

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
        
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def check_root(self, x, y):
        return self.find(x) == self.find(y)

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, e in enumerate(E):
        if j != i:
            uf.unite(e[0]-1, e[1]-1)
    
    if not uf.check_root(E[i][0]-1, E[i][1]-1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    ans = 0

    for i in range(edge_num):
        dic_graph = defaultdict(set)
        for j in range(edge_num):
            if i == j:
                continue
            dic_graph[data[j][0]].add(data[j][1])
            dic_graph[data[j][1]].add(data[j][0])
        if check(dic_graph, node_num):
            ans += 1

        # print(dic_graph)

    print(ans)

def check(dic_graph, node_num):
    visit_data = [0 for i in range(node_num + 1)]
    visit_data[0] = 1
    visit_data[1] = 1

    now_point = set()
    next_point = set()
    now_point.add(1)

    while len(now_point) > 0:
        for ele in now_point:
            next_data = dic_graph[ele]
            for next_ele in next_data:
                if visit_data[next_ele]:
                    continue
                next_point.add(next_ele)
                visit_data[next_ele] = 1
        now_point = next_point
        next_point = set()

    # print(visit_data)


    if 0 in visit_data:
        return 1
    else:
        return 0

if __name__ == '__main__':
    main()

Submission status: Accepted

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA), BridgeEdge(nodeB)]

class BridgeEdge:
    def __init__(self, node):
        self.node = node
        self.judge = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)


nodes = [Node(i) for i in range(N+1)]
bridges = []
for A, B in (map(int, input().split()) for _ in range(M)):
    b = Bridge(nodes[A], nodes[B])
    nodes[A].addEdge(b.edges[1])
    nodes[B].addEdge(b.edges[0])
    bridges.append(b)


s = [(None, nodes[1])]
idx = 0
while idx < len(s):
    pre, cur = s[idx]
    idx += 1

    for nxt in cur.bridges:
        if not pre is nxt.node and nxt.judge < 2:
            nxt.judge += 1
            s.append((cur, nxt.node))

cnt = 0
for bd in bridges:
    if sum(1 for b in bd.edges if b.judge <= 1) > 0:
        cnt += 1

print(cnt)

Submission status: Accepted

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA), BridgeEdge(nodeB)]

class BridgeEdge:
    def __init__(self, node):
        self.node = node
        self.judge = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)


nodes = [Node(i) for i in range(N+1)]
bridges = []
for A, B in (map(int, input().split()) for _ in range(M)):
    b = Bridge(nodes[A], nodes[B])
    nodes[A].addEdge(b.edges[1])
    nodes[B].addEdge(b.edges[0])
    bridges.append(b)


s = [(None, nodes[1], 1)]
idx = 0
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1

    if level > N * 2:
        break

    for nxt in cur.bridges:
        if not pre is nxt.node and nxt.judge < 2:
            nxt.judge += 1
            s.append((cur, nxt.node, level+1))

cnt = 0
for bd in bridges:
    if sum(1 for b in bd.edges if b.judge <= 1) > 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, M = map(int, input().split())
E = []
for _ in range(M):
    a, b = map(int, input().split())
    E.append((a, b))
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    edges = [e for j, e in enumerate(E) if j != i]
    for a, b in edges:
        uf.union(a-1, b-1)
    if len([v for v in uf.vertices if v < 0]) >= 2:
        ans += 1
print(ans)

Submission status: Accepted

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

def check(v):
    c[v] = 1
    for i in range(len(lst2)):
        if lst2[i][0]-1 == v and c[lst2[i][1]-1] == 0 and d[i] == 0:
            d[i] = 1
            check(lst2[i][1]-1)
        if lst2[i][1]-1 == v and c[lst2[i][0]-1] == 0 and d[i] == 0:
            d[i] = 1
            check(lst2[i][0]-1)
    return
    
count = 0
for i in range(M): #使わない橋を全探索
    c = [0] * N #到達したかのチェック
    d = [0]* (M-1) #確認した橋のチェック
    lst2 = lst[:i] + lst[i+1:] #使っても良い橋のリストを準備
    # print (lst2)
    check(0) #0からはじめて、繋がっているところを探索
    if 0 in c:
        count += 1
    else:
        pass
    
print (count)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, size):
    self.table = [-1 for _ in range(size)]
  
  def find(self, x):
    while self.table[x] >= 0:
      x = self.table[x]
    return x
  
  def union(self, x, y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s1] != self.table[s2]:
        if self.table[s1] < self.table[s2]:
          self.table[s2] = s1
        else:
          self.table[s1] = s2
      else:
        self.table[s1] += -1
        self.table[s2] = s1
    return 
  
n, m = map(int, input().split())  
edges = [list(map(int, input().split())) for i in range(m)]
ans = 0

for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i != j:
      uf.union(edges[j][0]-1, edges[j][1]-1)
      c = 0
  for j in range(n):
    if j == uf.find(j):
      c += 1
  if c > 1:
    ans += 1
print(ans)

Submission status: Accepted

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

def search(UF,loc):
    if UF[loc] == loc:
        return UF[loc]
    else:
        UF[loc] = search(UF,UF[loc])
        return UF[loc]
    

ans = 0

for i in range(m):
    aa,bb = AB[i]
    UF = [_ for _ in range(n+1)]
    for k in range(m):
        a,b = AB[k]
        if i!=k:
            UF[a] = search(UF,a)
            UF[b] = search(UF,b)
            if UF[a] != UF[b]:
                UF[max(UF[a],UF[b])] = UF[min(UF[a],UF[b])]
    for l in range(1,n+1):
        UF[l] = search(UF,l)
    for j in range(1,n):
        if UF[j] != UF[j+1]:
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

  def reset(self):
    self._parent=[n for n in range(0, n)]

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
ct=0
UF=UF(n)
for i in range(m):
  for j in range(m):
    if j!=i:
      UF.unite(l[j][0]-1,l[j][1]-1)
  if UF.groupnum()!=1:ct+=1
  UF.reset()
print(ct)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[list() for _ in range(n+1)]
side=[list(map(int,input().split())) for i in range(m)]
for a,b in side:
	g[a].append(b)
	g[b].append(a)
cnt=0
def dfs(x,s):
	ed[x-1]=1
	for i in g[x]:
		if s!={x,i} and ed[i-1]==0:dfs(i,s)
cnt=0
for i in range(m):
	ed=[0]*n
	dfs(1,set(side[i]))
	if 0 in ed:cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from collections import deque

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

edges = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().rstrip().split(' '))
    a -= 1
    b -= 1
    edges[a].append([b, i])
    edges[b].append([a, i])
    
count = 0
for i in range(M):
    v = [False] * N
    v[0] = True
    d = deque([0])
    while len(d) > 0:
        temp_v = d.popleft()
        for e in edges[temp_v]:
            if e[1] != i and v[e[0]] == False:
                d.append(e[0])
                v[e[0]] = True
            
    if sum(v) != N:
        count += 1
        
print(count)