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:
import copy
from collections import deque
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
ab = []
answer = 0
for _ in range(M):
    a, b = map(int, input().split())
    ab.append((a-1, b-1))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
# print(edge[0])
# print(ab)
for a, b in ab:
    lost_edge = copy.deepcopy(edge)
    # print(lost_edge)
    # print(a, b, edge)
    lost_edge[a].remove(b)
    lost_edge[b].remove(a)
    # print(lost_edge)

    seen = [0] * N
    seen[0] = 1
    todo = deque([0])
    while todo:
        cur_v = todo.pop()
        seen[cur_v] = 1
        for next_v in lost_edge[cur_v]:
            if not seen[next_v]:
                todo.append(next_v)
        # print(todo)
        # print(seen)
    if 0 in seen:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

n, m = map(int, input().split())
edges = []
graph = [ [] for _ in range(n) ]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    edges.append( (a, b) )

    graph[a].append(b)
    graph[b].append(a)

def dfs(u, v):
    is_visited = [ False ]*n
    st = []
    st.append(0)
    while st:
        cur = st.pop()
        is_visited[cur] = True
        for adj in graph[cur]:
            if is_visited[adj]: continue
            if cur == u and adj == v: continue
            if cur == v and adj == u: continue

            st.append(adj)

    return all(is_visited)

ans = 0
for u, v in edges:
    if not dfs(u, v):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from copy import deepcopy
from collections import Counter


def dfs(G, i, fr, color):
    color[i] = 1
    for node in G[i]:
        if node != fr and node != -1 and color[node] == -1:
            dfs(G, node, i, color)

def main():
    n, m = list(map(int, input().strip().split()))
    G = [[] for _ in range(n)]
    for i in range(m):
        a, b = list(map(int, input().strip().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    ans = 0
    for i, node in enumerate(G):
        for j, edge in enumerate(G[i]):
            D = deepcopy(G)
            D[i][j] = -1
            color = [-1] * n
            dfs(D, 0, -1, color)
            c = Counter(color)[1]
            if c != n:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def is_all_nodes_connected():
    q = deque()
    used = set()
    q.append(1)
    used.add(1)
    while len(q) > 0:
        prv_node = q.pop()
        for node in g[prv_node]:
            if node in used:
                continue
            else:
                q.append(node)
                used.add(node)
    if len(used) == N:
        return True
    else:
        return False


N, M = map(int, input().split())
g = {i: [] for i in range(1, N+1)}
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    AB.append([a, b])

ans = 0
for a, b in AB:
    g[a].remove(b)
    g[b].remove(a)
    if is_all_nodes_connected() is False:
        ans += 1
    g[a].append(b)
    g[b].append(a)

print(ans)

Submission status: Accepted

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

def dfs(num,visited):
    #print(visited)
    if num in visited and visited[-1]!=num:
        tree[num][visited[-1]]=-1
        tree[visited[-1]][num]=-1
        while visited[-1]!=num:
            temp=visited.pop(-1)
            #print(temp)
            tree[temp][visited[-1]]=-1
            tree[visited[-1]][temp]=-1
            start.append(temp)
            
    else:
        for index,item in enumerate(tree[num]):
            if item == 1:
                tree[num][index]=0
                tree[index][num]=0
                dfs(index,visited+[num])
    return 0

tree=[[0]*N for i in range(N)]

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

start=[0]

while start:
    #print(start[-1]+1)
    dfs(start.pop(-1),[])

cnt=0
for leaf in tree:
    cnt+=leaf.count(-1)

print(M-cnt//2)

Submission status: Accepted

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

ans = 0
for rep in range(m):
    d = [[10 ** 18] * n for i in range(n)]
    for i in range(n):
        d[i][i] = 0

    for i in range(m):
        if i == rep:
            continue
        a, b = edge[i]
        d[a][b] = 1
        d[b][a] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    ok = 0
    for i in range(n):
        for j in range(n):
            if d[i][j] == 10 ** 18:
                ok = 1
    ans += ok

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    AB = []
    V = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        AB.append([a, b])
        V[a].append(b)
        V[b].append(a)


    ans = 0
    for a, b in AB:
        visited = set()

        q = collections.deque()
        q.append(1)
        visited.add(1)

        while q:
            c = q.pop()
            for i in V[c]:
                if i in visited:
                    continue
                if (a == i and b == c) or (a == c and b == i):
                    continue
                else:
                    q.append(i)
                    visited.add(i)

        if len(visited) != N:
            ans += 1

    print(ans)









if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(n,G):
    visited = [False] * n
    visited[0] = True
    stack = [0]
    while len(stack) != 0:
        x = stack.pop()
        visited[x] = True
        for i in G[x]:
            if visited[i] == True:
                continue
            stack.append(i)
    if not False in visited:
        return False
    return True

def main():
    n,m = map(int,input().split())
    G = [list() for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        a = a - 1
        b = b - 1
        G[a].append(b)
        G[b].append(a)
    ans = 0
    for i in range(n):
        for j in range(i + 1,n):
            if not j in G[i]:
                continue
            G[i].remove(j)
            G[j].remove(i)
            if solve(n,G):
                ans = ans + 1
            G[i].append(j)
            G[j].append(i)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for _ in range(M):
    a, b = [int(x) for x in input().split()]
    G[a].append(b)
    G[b].append(a)
    
ans = 0
for _ in range(M):
    for i in range(1, N + 1):
        if len(G[i]) == 1:
            tmp = G[i][0]
            G[i].remove(tmp)
            G[tmp].remove(i)
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
graph = [[]for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
pre = [0]+[-1]*(n-1)
low = [10**9]*n
def dfs(now,last,pre,low,cnt,bri):
    cnt+=1
    pre[now] = cnt
    low[now] = pre[now]
    for next in graph[now]:
        
        
    
        if pre[next] == -1:
            low[now] = min(low[now],dfs(next,now,pre,low,cnt,bri))
            if low[next] == pre[next]:
                bri.append((now,next))
        else:
            if next == last:continue
            low[now] = min(low[now],low[next])
    return low[now]        
          
      
bri = []
cnt = 0
dfs(0,-1,pre,low,cnt,bri)
print(len(bri))

Submission status: Accepted

Solution code:
# 単純に橋となる辺を返す
def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p):
        nonlocal gen
        res = 0
        for v in G[u]:
            if v == p:
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                r = dfs(v, u)
                if r == 0:
                    result.add((u, v) if u < v else (v, u))
                res += r
        res -= cost[u]
        return res
    for v in range(N):
        if not label[v]:
            label[v] = gen; gen += 1
            r = dfs(v, -1)
            assert r == 0, r
    return result

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

print(len(bridge(G, N)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ab = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab.append([a,b])
    
def bfs(ab):
    from collections import deque
    que = deque()
    alr = [0]
    que.append(0)
    while que:
        q = que.popleft()
        for i in ab[q]:
            if i not in alr:
                alr.append(i)
                que.append(i)
    if len(alr) < N:
        return 1
    else:
        return 0

count = 0
for i in range(M):
    ab2 = [[] for k in range(N)]
    for j in range(M):
        if j != i:
            a,b = ab[j]
            ab2[a].append(b)
            ab2[b].append(a)
    count += bfs(ab2)
print(count)

Submission status: Accepted

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

edge = [[0] * n for _ in range(n)]
for _ in range(m):
   a, b = map(int, input().split())
   a -= 1
   b -= 1
   edge[a][b] = 1
   edge[b][a] = 1

def dfs(v):
   visited[v] = 1
   for k in range(n):
      if (edge[v][k] == 0):
         continue
      if (visited[k] == 1):
         continue
      dfs(k)


ans = 0
for i in range(n):
   for j in range(i+1, n):
      if (edge[i][j] == 1):
         edge[i][j] = 0
         edge[j][i] = 0
         # dfs
         visited = [0 for _ in range(n)]
         dfs(0)
         if (sum(visited) < n):
            ans += 1
         edge[i][j] = 1
         edge[j][i] = 1
print(ans)

Submission status: Accepted

Solution code:
import sys

class graph:
  def __init__(self):
    nm = input().split()
    # # vertices
    self.nv = int(nm[0])
    # # edges
    self.ne = int(nm[1])
    # vertices
    self.vertices = [i for i in range(self.nv)]
    # edge [edge id][0,1]
    self.edges = [[0, 0] for i in range(self.ne)]
    # accessible_edge [vertex id][connected vertex id]
    self.accessible_edge = [[] for i in range(self.nv)]
    for i in range(self.ne):
      e = list(map(lambda x: int(x)-1, input().split()))
      self.edges[i] = e
      self.accessible_edge[e[0]].append(e[1])
      self.accessible_edge[e[1]].append(e[0])
  
  def remove_edge(self, i):
    removed_accessible_edge = [[] for i in range(self.nv)]
    for j in range(self.ne):
      if j!=i:
        e = self.edges[j]
        removed_accessible_edge[e[0]].append(e[1])
        removed_accessible_edge[e[1]].append(e[0])
    return removed_accessible_edge

  def BFS(self, mod_edge):
    visited = [False for i in range(self.nv)]
    queue = []

    #initial id
    I = 0
    # stack, [0]=  vertex id, [1] = # searched children index
    queue.append(I)
    visited[I] = True
    while len(queue)!=0:
      # vertex id
      vid = queue.pop(0)
      # print(vid+1)
      v_edges = mod_edge[vid]
      # if not all([visited[e] for e in v_edges]):
      for e in v_edges:
        if not visited[e]:
          visited[e] = True
          queue.append(e)
    return all(visited)
    

if __name__ == "__main__":
  g = graph()
  count = 0
  g.BFS(g.accessible_edge)
  for i in range(g.ne):
    mod_edge = g.remove_edge(i)
    # print(mod_edge)
    count += 1 if not g.BFS(mod_edge) else 0
  print(count)

Submission status: Accepted

Solution code:
import sys

class graph:
  def __init__(self):
    nm = input().split()
    # # vertices
    self.nv = int(nm[0])
    # # edges
    self.ne = int(nm[1])
    # vertices
    self.vertices = [i for i in range(self.nv)]
    # edge [edge id][0,1]
    self.edges = [[0, 0] for i in range(self.ne)]
    # accessible_edge [vertex id][connected vertex id]
    self.accessible_edge = [[] for i in range(self.nv)]
    for i in range(self.ne):
      e = list(map(lambda x: int(x)-1, input().split()))
      self.edges[i] = e
      self.accessible_edge[e[0]].append(e[1])
      self.accessible_edge[e[1]].append(e[0])
  
  def remove_edge(self, i):
    removed_accessible_edge = [[] for i in range(self.nv)]
    for j in range(self.ne):
      if j!=i:
        e = self.edges[j]
        removed_accessible_edge[e[0]].append(e[1])
        removed_accessible_edge[e[1]].append(e[0])
    return removed_accessible_edge

  def DFS(self, mod_edge):
    visited = [False for i in range(self.nv)]
    stack  = []

    #initial id
    I = 0
    # stack, [0]=  vertex id, [1] = # searched children index
    stack.append(I)
    visited[I] = True
    while len(stack)!=0:
      # vertex id
      vid = stack.pop(0)
      # print(vid+1)
      v_edges = mod_edge[vid]
      # if not all([visited[e] for e in v_edges]):
      for e in v_edges:
        if not visited[e]:
          visited[e] = True
          stack.append(e)
    return all(visited)
    

if __name__ == "__main__":
  g = graph()
  count = 0
  for i in range(g.ne):
    mod_edge = g.remove_edge(i)
    # print(mod_edge)
    count += 1 if not g.DFS(mod_edge) else 0
  print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
T = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

ans = M
for a, b in AB:
    a -= 1
    b -= 1
    T[a].remove(b)
    T[b].remove(a)
    visited = [False] * N
    def rec(x):
        visited[x] = True
        for y in T[x]:
            if not visited[y]:
                rec(y)
    rec(0)
    ans -= all(visited)
    T[a].append(b)
    T[b].append(a)
print(ans)

Submission status: Accepted

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

def size0find():
    global x,n
    next=[]
    for i in range(n):
        if len(x[i])==1:
            next.append(i)
            k=x[i][0]
            x[i].remove(k)
            x[k].remove(i)
    return next

cnt=0
while True:
    y=size0find()
    l=len(y)
    if l==0:
        break
    cnt+=l
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    def f(a, b):
        ab = set([a, b])
        stack = [a]
        done = set()
        while stack:
            u = stack.pop()
            for v in g[u]:
                if u in ab and v in ab:
                    continue
                if v not in done:
                    done.add(v)
                    stack.append(v)
        return b not in done

    c = 0
    for a, b in AB:
        if f(a, b):
            c += 1

    return c


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
G = [[0]*n for _ in range(n)]
E = []
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    G[a][b] = 1
    G[b][a] = 1
    E.append((a,b))

ans = 0
for e in E:
    del_a, del_b = e
    
    #対象の辺を消す
    G[del_a][del_b] = 0
    G[del_b][del_a] = 0
    
    que = ([0])
    visited = [False]*n
    while que:
        node = que.pop()
        if visited[node] == True:
            continue
        visited[node] = True
        for j in range(n):
            if G[node][j] == 1:
                que.append(j)
    if False in visited:
        ans += 1
    
    #対象の辺を戻す
    G[del_a][del_b] = 1
    G[del_b][del_a] = 1
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
path=[set() for i in range(N+1)]
for a,b in AB:
    path[a].add(b)
    path[b].add(a)
path=[list(i) for i in path]

stack=[[1,[1]]]
itta=set([1])

notBridge=set()
while stack:
    ten,totyuu=stack[-1]
    #print(stack)
    if not path[ten]:
        stack.pop()
        continue
    miti=path[ten].pop()
    if not miti in itta:
        stack.append([miti,totyuu+[miti]])
        itta.add(miti)
    elif len(totyuu)>1 and totyuu[-2]==miti:
        pass
    else:
        flag=0
        Z=totyuu+[miti]
        #totyuu+=[miti]
        for i in range(len(Z)-1):
            if miti==Z[i]:
                flag=1
            if flag:
                notBridge.add(Z[i]*100+Z[i+1] if Z[i]<Z[i+1] else Z[i]+Z[i+1]*100)
print(M-len(notBridge))

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
graph = [[] * N for _ in range(N)]
uv = [list(map(int, input().split())) for _ in range(M)]

ans = 0
for i in range(M):
    graph = [[] * N for _ in range(N)]
    for k in range(M):
        if k == i:
            continue
        u = uv[k][0] - 1
        v = uv[k][1] - 1
        graph[u].append(v)
        graph[v].append(u)
    
    # BFSのためのデータ構造
    dist = [False for _ in range(N)]
    que = deque()

    # 初期条件
    dist[0] = True
    que.append(0)

    # BFS開始
    while que:
        v = que[0]
        que.popleft()
        for new_v in graph[v]:
            if dist[new_v]:
                continue
            # 探索した頂点はTrueにする
            dist[new_v] = True
            que.append(new_v)
    
    if False in dist:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:

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

edges = [[] for i in range(N + 1)]
bridges = []

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


ans = 0

for i in range(M):
  colors = ["white"] * (N + 1)
  u = bridges[0][0]
  stack = [u]
  a, b = map(int, bridges[i])

  while stack:
    u = stack.pop()
    colors[u] = "black"

    for v in edges[u]:
      if a == u and b == v:
        continue
      if b == u and a == v:
        continue
      if colors[v] != "black":
        stack.append(v)
  
  if len(list(filter(lambda x: x == "white" ,colors))) >= 2:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N, M = map(int, input().split())
graph = [[False for i in range(N)] for j in range(N)]
visited = [False for i in range(N)]
def dfs(v):
    visited[v] = True
    for k in range(N):
        # 橋がなければわたらない
        if not graph[v][k]:
            continue
        # すでに訪れていたら渡らない
        if visited[k]:
            continue
        dfs(k)
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    # 橋をTrueとして表す
    graph[a][b] = True
    graph[b][a] = True 

ans = 0
# a, bの橋が通れないとして都度DFSを実行
for a, b in zip(A, B):
    graph[a][b] = False
    graph[b][a] = False
    visited = [False for i in range(N)]
    dfs(0)
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    # 渡れない島があったら+1
    if bridge:
        ans += 1
    graph[a][b] = True
    graph[b][a] = True
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N, M = map(int, input().split())
graph = [[False for i in range(N)] for j in range(N)]
visited = [False for i in range(N)]
def dfs(v):
    visited[v] = True
    for k in range(N):
        if not graph[v][k]:
            continue
        if visited[k]:
            continue
        dfs(k)
A, B = [], []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    graph[a][b] = True
    graph[b][a] = True 

ans = 0
for a, b in zip(A, B):
    graph[a][b] = False
    graph[b][a] = False
    visited = [False for i in range(N)]
    dfs(0)
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    if bridge:
        ans += 1
    graph[a][b] = True
    graph[b][a] = True
print(ans)

Submission status: Accepted

Solution code:
"""import sys
input = sys.stdin.readline()"""
n,m=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)
ab=[]
for i in range(m):
    a,b=map(int,input().split())
    ab.append([a,b])
cnt=0
for i in range(m):
    uf=UnionFind(n+1)
    for j in range(m):
        a=ab[j][0]
        b=ab[j][1]
        if i==j:continue
        uf.union(a,b)
    if not uf.same(ab[i][0],ab[i][1]):
        cnt+=1
print(cnt)

Submission status: Accepted

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

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

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

N, M = MAP()
ab = [LIST() for _ in range(M)]

graph = [[] for _ in range(N)]

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

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

Submission status: Accepted

Solution code:
import queue

n,m = map(int,input().split())
li = [[0 for _ in range(n)] for i in range(n)]
edge = []

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

def jdg(a,b,ans):
    li[a][b] = 0
    li[b][a] = 0

    srch = [0 for i in range(n)]
    q = queue.Queue()
    q.put(0)
    while(not q.empty()):
        memo = q.get()
        if srch[memo]==1:
            continue

        for i in range(n):
            if li[memo][i]==1:
                q.put(i)
        srch[memo] = 1

    #print(a,b,srch)
    if 0 in srch:
        ans += 1
    
    li[a][b] = 1
    li[b][a] = 1

    return ans

ans = 0
for i in range(len(edge)):
    ans = jdg(edge[i][0],edge[i][1],ans)
    #print(ans)

print(ans)

Submission status: Accepted

Solution code:
# 発想はわかったが実装まで出来なかった
N, M = list(map(int, input().split()))
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))

ans = 0

def dfs(x):
    visited[x] = True
    for i in range(len(graph[x])):
        if visited[graph[x][i]]:
            continue
        else:
            dfs(graph[x][i])

for i in range(M):
    visited = [False for k in range(N + 1)]
    visited[0] = True
    graph = [[] for k in range(N + 1)]
    for j in range(M):
        if j != i:
            graph[ab[j][0]].append(ab[j][1])
            graph[ab[j][1]].append(ab[j][0])
    dfs(1)

    for j in range(N + 1):
        if visited[j]:
            continue
        else:
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
ab=[]
for i in range(M):
    ab.append(list(map(int,input().split())))

ans=0

def dfs(x):
    flg[x]=True
    for i in range(len(G[x])):
        
        if flg[G[x][i]]:
            continue
        else:
            dfs(G[x][i])

for i in range(M):
    flg=[False for k in range(N+1)]
    flg[0]=True
    G=[[] for k in range(N+1)]
    for j in range(M):
        if j!=i:
            G[ab[j][0]].append(ab[j][1])
            G[ab[j][1]].append(ab[j][0])
    dfs(1)
    
    for j in range(N+1):
        if flg[j]:
            continue
        else:
            ans+=1
            break

print(ans)

Submission status: Accepted

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

def search(remove_edge):
    Q = [(-1,0)]
    visited = [False for j in range(N)]
    visited[0] = True
    while Q:
        a,b = Q.pop()
        for e in edges[b]:
            if remove_edge[0] == b and remove_edge[1] == e:
                pass
            elif remove_edge[1] == b and remove_edge[0] == e:
                pass
            elif e == a:
                pass
            elif visited[e]:
                pass
            else:
                visited[e] = True
                Q.append((b,e))
    if False in visited:
        return True
    else:
        return False

ans = 0
for e in edges_2:
    if search(e):
        ans += 1
print(ans)

Submission status: Accepted

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



def dfs(start, edges, exception):
    seen = [False] * n
    seen[start] = True
    todo = []
    for to in edges[start]:
        if [start, to] in exception:
            continue
        todo.append(to)

    while todo:
        node = todo.pop()
        if seen[node]:
            continue

        seen[node] = True
        for to in edges[node]:
            if [node, to] in exception:
                continue
            todo.append(to)

    if sum(seen) == n:
        return False
    else:
        return True


ans = 0
for exception in check:
    ans += dfs(0, edges, exception)

print(ans)

Submission status: Accepted

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


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

ans = 0
for edge in edges:
    seen = [False] * N
    copied_graph = copy.deepcopy(graph)
    copied_graph[edge[0]].remove(edge[1])
    copied_graph[edge[1]].remove(edge[0])
    dfs(copied_graph,0)
    if not all(seen):
        ans += 1

print(ans)

Submission status: Accepted

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

def dfs(A,n):
    for a in A[n]:
        if visited[a-1] == -1:
            visited[a-1] = 1
            dfs(A,a-1)
    if -1 in visited:
        return True
    else:
        return False

ans = 0 
for i in range(M):
    A = [[] for _ in range(N)]
    edges_new = edges[:i] + edges[i+1:]
    for a,b in edges_new:
        A[a-1].append(b)
        A[b-1].append(a)
    visited = [-1]*N
    visited[0] = 1
    if dfs(A,0):
        ans += 1
print(ans)