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:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja
# unionfind or 深さ優先探索


class UnionFind:
    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 根がルートの時は、グループの要素数を格納　最初は全て根で要素数1
        self.parents = [-1] * n

    # 再帰 groupの根を返す
    # 経路圧縮あり
    def find(self, x):
        # 0より小さい場合は根
        if self.parents[x] < 0:
            # indexを返す
            return x
        else:
            # 根になるまで親を辿る
            # 経路圧縮 根のindexが全ての親に再帰的につく
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # groupを併合
    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
        # 根のグループ数を追加 xの方グループの要素数が多い前提なので多い方に寄せる
        self.parents[x] += self.parents[y]
        # 親(根)のindexを入れる
        self.parents[y] = x

    # 根が同じか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 全ての根の要素を返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())


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

edge = []
for _ 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, (a, b) in enumerate(edge):
        if i == j:
            continue
        uf.union(a, b)
    if uf.group_count() == 1:
        ans += 1

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


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

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j, (a, b) in enumerate(bridge):
        if i == j:
            continue
        uf.union(a,b)
    if uf.group_count() == 2:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
a, b = map(int,input().split())
v = []
for _ in range(b):
    aa,bb = map(int, input().split())
    v.append([aa-1, bb-1])
res = 0
for i in range(b):
    visited = [False] * a
    curv = []
    for j in range(a):
        curv.append([])
    for j in range(b):
        if i == j:
            continue
        else:
            x, y = v[j]
            curv[x].append(y)
            curv[y].append(x)
    import collections
    q = collections.deque([])
    q.append(0)

    while len(q) > 0:
        curnode = q.pop()
        if visited[curnode] is True:
            continue

        visited[curnode] = True
        for j in range(len(curv[curnode])):
            nextnode = curv[curnode][j]
            if visited[nextnode] is False:
                q.append(nextnode)

    isbridge = False
    for j in range(a):
        if visited[j] is False:
            isbridge = True
    if isbridge:
        res += 1

print(res)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import coo_matrix
import numpy as np

N,M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
I,J = zip(*edges)

g = coo_matrix(([1]*M, (I,J)), (N+1, N+1))
g = g.tolil()

ans = 0
for i,j in edges:
    g[i,j] = 0
    cnt, _ = connected_components(g, directed=False)
    g[i,j] = 1
    ans += (cnt > 2)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n, m = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    L = []
    for _ in range(m):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        G[a].append(b)
        G[b].append(a)
        L.append(set([a, b]))
    ans = 0
    for l in L:
        stack = deque([0, ])
        visited = [False] * n
        while stack:
            x = stack.popleft()
            if visited[x]:
                continue
            visited[x] = True
            for dx in G[x]:
                if set([x, dx]) == l:
                    continue
                if not visited[dx]:
                    stack.append(dx)
        if not all(visited):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self._n = n
        self._table = [-1]*n
        self._rank = [0]*n

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        elif self._rank[x] > self._rank[y]:
            self._table[x] += self._table[y]
            self._table[y] = x
        else:
            self._table[y] += self._table[x]
            self._table[x] = y
            if self._rank[x] == self._rank[y]:
                self._rank[y] += 1
    
    def find(self, x, y):
        return self._root(x) == self._root(y)

    def count(self, x):
        return -self._table[self._root(x)]
    
    def __str__(self):
        return str(list(self))
    def __repr__(self):           
        return repr(list(self))
    def __iter__(self):
        return (self._root(i) for i in range(n))

n, m, *AB = map(int, open(0).read().split())
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j, (a, b) in enumerate(zip(AB[::2], AB[1::2])):
        if i == j:
            continue
        uf.unite(a-1, b-1)
    ans += len(set(uf)) != 1
print(ans)

Submission status: Accepted

Solution code:
[n,m] = [int(i) for i in input().split()]
ans = 0
ab = []
stage = [[0] * n for i in range(n)]
for i in range(m):
    ab.append([int(j)-1 for j in input().split()])
    stage[ab[-1][0]][ab[-1][1]] = 1
    stage[ab[-1][1]][ab[-1][0]] = 1
for i in range(m):
    visit = [0] * n
    now = 0
    stage[ab[i][0]][ab[i][1]] = 0
    stage[ab[i][1]][ab[i][0]] = 0
    next = [0]
    while len(next):
        now = next.pop()
        visit[now] = 1
        for j in range(n):
            if stage[now][j] == 1 and visit[j] != 1:
                next.append(j)

    stage[ab[i][0]][ab[i][1]] = 1
    stage[ab[i][1]][ab[i][0]] = 1



    if 0 in visit:
        ans += 1
print(ans)

Submission status: Accepted

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

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

def ne(now,s,visit):
  visit.append(now)
  for i in e[now]:
    if i not in visit:
      ne(i, s, visit[:])
    elif len(visit)>2 and s==i:
      v1=visit[1]
      v2=visit[-1]
      if [s,v1] in b: b.remove([s,v1])
      elif [v1,s] in b: b.remove([v1,s])
      if [s,v2] in b:b.remove([s,v2])
      elif [v2,s] in b:b.remove([v2,s])
      break

for i in range(n):
  ne(i,i,[])
print(len(b))

Submission status: Accepted

Solution code:
from collections import deque

def Graph(ab):
    G = [[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

def dfs(G, a, b):
    #(a, b)は除外する辺
    q = deque()
    q.append((1,-1))
    log = [0] * n
    log[0] = 1
    while q:
        V, P = q.pop()
        for new_v in G[V-1]:
            if {a, b} == {new_v, V}:#除外する辺であれば
                continue
            if new_v == P:#戻らない
                continue
            if log[new_v - 1]:#過去に行った頃がある点に行かない。
                continue
            log[new_v - 1] = 1
            q.append((new_v,V))
    return sum(log) != n

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
G = Graph(ab)

ans = 0
for a, b in ab:
    if dfs(G, a, b):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
n,m=map(int,input().split())
edges=[list(map(int,input().split()))for i in range(m)]
a=0
for i in range(m):
    uf=UnionFind(n,1)
    for j in  range(m):
        if j==i:continue
        uf.unite(*edges[j])
    a+=uf.connected()
print(m-a)

Submission status: Accepted

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

def root(par, a):
    a_ = a
    while par[a] != a:
        a = par[a]
    par[a_] = a
    return a

def unite(par, a, b):
    ar = root(par, a)
    br = root(par, b)
    if ar != br:
        par[ar] = br

ans = 0
for i in range(M):
    par = list(range(N))
    for j in range(M):
        if i == j:
            continue
        a, b = E[j]
        unite(par, a, b)

    r0 = root(par, 0)
    for k in range(1, N):
        if root(par, k) != r0:
            ans += 1
            break
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(M):
    G = [set() for _ in range(N)]
    for j in range(M):
        if i == j:
            continue
        a, b = E[j]
        G[a].add(b)
        G[b].add(a)

    todo = [0]
    done = set()
    while todo:
        p = todo.pop()
        done.add(p)
        for np in G[p]:
            if not np in done:
                todo.append(np)

    if len(done) < N:
        ans += 1
print(ans)

Submission status: Accepted

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

def dfs(start):
    if visited[start]:
        return
    visited[start] = 1
    for i in range(n):
        if edges[start][i]:
            dfs(i)

ans = m
# edgeを一つづつ見ていく
for i in range(n-1):
    for j in range(i+1, n):
        if not edges[i][j]:
            continue
        # エッジを削除した場合に、連結しているかをdfsで確認
        #   visited: 訪れたかどうかを表す変数
        visited = [0] * n
        edges[i][j] = 0
        edges[j][i] = 0
        dfs(0)
        # お片付け、削除したedgeを元に戻しておく
        edges[i][j] = 1
        edges[j][i] = 1
        # 全て訪れられていたら、そのエッジはなくても非連結にならないので、bridgeではない
        if sum(visited) == n:
            ans -=1

print(ans)

Submission status: Accepted

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

def dfs(start):
    if visited[start]:
        return
    visited[start] = 1
    for i in range(n):
        if edges[start][i]:
            dfs(i)

ans = m
# edgeを一つづつ見ていく
for i in range(m-1):
    for j in range(i+1, m):
        if not edges[i][j]:
            continue
        # エッジを削除した場合に、連結しているかをdfsで確認
        #   visited: 訪れたかどうかを表す変数
        visited = [0] * n
        edges[i][j] = 0
        edges[j][i] = 0
        dfs(0)
        # お片付け、削除したedgeを元に戻しておく
        edges[i][j] = 1
        edges[j][i] = 1
        # 全て訪れられていたら、そのエッジはなくても非連結にならないので、bridgeではない
        if sum(visited) == n:
            ans -=1

print(ans)

Submission status: Accepted

Solution code:
import collections
import queue
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y = [0] * M, [0] * M
g = [[] for _ in range(N)]

for i in range(M):
    X[i], Y[i] = map(int, input().split())

    X[i] -= 1
    Y[i] -= 1
    g[X[i]].append(Y[i])
    g[Y[i]].append(X[i])


def bfs(x, y):
    visited = [False] * N
    q = queue.Queue()
    for nx in g[x]:
        if nx == y:
            continue
        q.put(nx)
        visited[nx] = True

    visited[x] = True

    while not q.empty():
        cur = q.get()
        if cur == y:
            return True

        for nx in g[cur]:
            if visited[nx]:
                continue
            q.put(nx)
            visited[nx] = True

    return False


cnt = 0
for i in range(M):
    if not bfs(X[i], Y[i]):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from functools import reduce

# judge if the list contains false. 
def is_all_true(arg):
  if isinstance(arg, bool):
    return arg
  return reduce(lambda x, y: is_all_true(x) and is_all_true(y), arg)

N, M = list(map(int, input().split()))
# list with from and to as elements.
lines_ft = []
for _ in range(M):
  _from, _to = list(map(int, input().split()))
  lines_ft.append((_from, _to))

reachable_counter = 0
# simulation of whether all the islands can be reached when each line is excluded.
for i in range(M):
  # generated per simulation.
  is_reachable = [[False if i != j else True for i in range(N)] for j in range(N)]
  # init by excluding the current lines.
  for f, t in lines_ft[:i] + lines_ft[i + 1:]:
    is_reachable[f - 1][t - 1] = True
    is_reachable[t - 1][f - 1] = True
  # simulate by a list that excludes one line.
  for k in range(N):
    for i in range(N):
      for j in range(N):
        is_reachable[i][j] = is_reachable[i][j] or (is_reachable[i][k] and is_reachable[k][j])
  # verify that there is an unreachable island.
  if not is_all_true(is_reachable):
    reachable_counter += 1

print(reachable_counter)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# N頂点M辺のグラフ
# 自己ループ (a1==b1)は存在しない
# 二重辺(a1,b1 と a2,b2が同じもの)は存在しない
# 一辺取り除いた時に分離してしまう辺を橋と呼ぶ


# union find
# 最初は全て値であるとして初期化する parents[i] = i

# root(x) => xの根を返す関数
# unit(x,y) => root(x)とroot(y)が同じであればそのまま。違う場合は、xの根であるroot(x)をyの根であるroot(y)につける. 根が同じでない二つの木を合併する。
# same(x,y) => 二つのデータx,yが属する木が同じ場合、trueを返す。if root(x) == root(y)するだけ
parents = None


def root(x):
    if parents[x] == x:
        return x
    parents[x] = root(parents[x])
    return parents[x]


count = 0


def unit(x, y):
    root_x = root(x)
    root_y = root(y)
    if root_x < root_y:
        parents[root_y] = root_x
    else:
        parents[root_x] = root_y


def same(x, y):
    root_x = root(x)
    root_y = root(y)
    return (root_x == root_y)


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

ans = 0
for i in range(M):
    parents = [k for k in range(N)]
    for j, e in enumerate(es):
        if j == i:
            continue
        a, b = e
        unit(a, b)
    a, b = es[i]
    if not same(a, b):
        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())
path = [list(map(int, input().split())) for i in range(M)]
ans = 0
for i in range(M):
    flag = 1
    bridge = UnionFind(N)
    for j in range(M):
        if i != j:
            bridge.union(path[j][0]-1, path[j][1]-1)
    for j in range(N):
        if not(bridge.same(0, j)):
            
            flag = 0
    if not(flag):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)


def dfs(x):
    if arrival[x-1]==1:
        return
    else:
        arrival[x-1]=1
        for i in mapi[x-1]:
            dfs(i)
        return

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

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

count=0
for i in range(m):
    li=l[0:i]+l[i+1:m]
    mapi=[[] for a in range(n)]
    for j in range(m-1):
        mapi[li[j][0]-1].append(li[j][1])
        mapi[li[j][1]-1].append(li[j][0])
    arrival=[0 for a in range(n)]
    dfs(1)
    if 0 in arrival:
        count+=1
print(count)

Submission status: Accepted

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

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):
  ra = root(a)
  rb = root(b)
  if ra == rb:
    return
  parent[ra] = rb

ans = 0
for i in range(M):
  parent = [k for k in range(N)]
  for j,e in enumerate(es):
    if j == i:
      continue
    a,b = e
    unite(a,b)
  a,b = es[i]
  if not is_same(a,b):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    XY = [il() for _ in range(M)]

    ret = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if i != j:
                x, y = XY[j]
                uf.unite(x - 1, y - 1)
        x, y = XY[i]
        if not uf.same(x - 1, y - 1):
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
ans = 0
roads = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
  G = [[]*N for _ in range(N)]
  for j in range(M):
    if j == i:
      continue
    a, b = roads[j]
    G[a-1].append(b-1)
    G[b-1].append(a-1)
  
  stack = deque([0])
  visited = [False] * N
  visited[0] = True
  while stack:
    now = stack.pop()
    for nxt in G[now]:
      if visited[nxt]:
        continue
      visited[nxt] = True
      stack.append(nxt)
      
  for f in visited:
    if not f:
      ans += 1
      break
      
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
l = []
for _ in range(M):
    a,b = list(map(int, input().split()))
    l.append([a-1,b-1])
visit = [0]*N
graph = [0]*N*N
g = []
def dfs(v):
  visit[v] = 1
  for v2 in range(N):
    if graph[v*N+v2] == 1 and visit[v2] == 0:
      g.append(v2)
    if v2 == N-1 and len(g) != 0:
      a = g[0]
      g.pop(0)
      return dfs(a)
ans = 0
for a,b in l:
  graph[a*N+b] = graph[b*N+a] = 1
for a,b, in l:
  graph[a*N+b] = graph[b*N+a] = 0
  visit = [0]*N
  dfs(0)
  if sum(visit) != N:
    ans += 1
  graph[a*N+b] = graph[b*N+a] = 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def dfs(s, graph, bridge, visit):
    visit[s] = True
    for next in graph[s]:
        if not bridge[s][next]: continue
        if visit[next]: continue
        dfs(next, graph, bridge, visit)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    graph = {n: [] for n in range(N)}

    for _ in range(M):
        a, b = il()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    ret = 0
    bridge = {n: [True] * N for n in range(N)}
    searched = {n: [False] * N for n in range(N)}
    for i in range(N):
        for j in graph[i]:
            if searched[i][j]: continue
            searched[i][j],searched[j][i] = True, True
            visit = [False] * N
            bridge[i][j],bridge[j][i] = False, False
            dfs(0, graph, bridge, visit)
            if not all(visit): ret += 1
            bridge[i][j], bridge[j][i] = True, True
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def dfs(s, graph, bridge, visit):
    visit[s] = True
    for next in graph[s]:
        if not bridge[s][next]: continue
        if visit[next]: continue
        dfs(next, graph, bridge, visit)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    graph = {n: [] for n in range(N)}

    for _ in range(M):
        a, b = il()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    ret = 0
    bridge = {n: [True] * N for n in range(N)}
    for i in range(N):
        for j in graph[i]:
            visit = [False] * N
            bridge[i][j],bridge[j][i] = False, False
            dfs(0, graph, bridge, visit)
            if not all(visit): ret += 1
            bridge[i][j], bridge[j][i] = True, True
    print(ret//2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(node, visited, g):
    visited[node] = True
    for neib in g[node]:
        if not visited[neib]:
            dfs(neib, visited,g)


N, M = map(int, input().split()) 
abl = []
for _ in range(M):
    a, b = map(int, input().split()) 
    abl.append([a,b])

ans = 0
for i in range(M):
    g = [ [] for _ in range(N+1)]
    for j, ab in enumerate(abl):
        if j == i: continue
        a,b = ab
        g[a].append(b)
        g[b].append(a)
    visited = [False] * (N+1)
    visited[0] = True
    dfs(1, visited, g)
    if False in visited:
        ans+=1 

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


def main():
    N, M = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(M)]
    # 辺を取っ払っても、そのノードに移動出来る時は橋となる？

    ans = 0
    for i in range(M):
        g = Graph()
        for j in range(M):
            if j == i:
                continue
            else:
                g.add_edge(ab[j][0], ab[j][1])
                g.add_edge(ab[j][1], ab[j][0])
        tmp = Dijkstra(g, ab[i][0])
        if tmp.shortest_distance(ab[i][1]) == float('inf'):
            ans += 1

    print(ans)


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 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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())


def main():
    n, m = map(int, input().split())
    a, b = [], []
    for i in range(m):
        A, B = map(int, input().split())
        a.append(A - 1)
        b.append(B - 1)
    
    ans = 0
    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if i == j:
                continue
            uf.union(a[j], b[j])
        if uf.group_count() != 1:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()