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:
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:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        '''
        要素xが属するグループの根を返す
        '''
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        '''
        要素xが属するグループと要素yが属するグループとを併合する
        '''
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        '''
        要素xが属するグループのサイズ（要素数）を返す
        '''
        return -self.parents[self.find(x)]

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

    def members(self, x):
        '''
        要素xが属するグループに属する要素をリストで返す
        '''
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        '''
        各要素の親要素の番号を格納するリスト
        '''
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        '''
        グループの数を返す
        '''
        return len(self.roots())

    def all_group_members(self):
        '''
        {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        '''
        return {r: self.members(r) for r in self.roots()}

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

ans = 0
for i in range(M):
    G = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j]
        a, b = a-1, b-1
        G.union(a, b)
    if G.group_count() > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

edges = [list(map(int, input().split())) for _ in range(M)]
od = [-1]*(N+1)
low = [-1]*(N+1)
pa = [0]*(N+1)
od[1] = 0
low[1] = 0
pa[1] = 1
ni = {i:[] for i in range(1,N+1)}

for i in range(M):
  ni[edges[i][0]].append(edges[i][1])
  ni[edges[i][1]].append(edges[i][0])

rlt = 0
h = deque([])
for i in ni[1]:
  h.append([1,i])

i = 0
while h:
  a = h.pop()
  if od[a[1]] > -1:
    if od[a[1]] < od[a[0]]:
      low[a[0]] = od[a[1]]
      c = a[0]
      while low[pa[c]] > od[a[1]]:
        low[pa[c]] = od[a[1]]
        c = pa[c]
  else:
    i += 1
    od[a[1]] = i
    low[a[1]] = i
    pa[a[1]] = a[0]
    for b in ni[a[1]]:
      if b == a[0]:
        continue
      h.append([a[1],b])
          
for i in range(2,N+1):
  if od[pa[i]] < low[i]:
    rlt += 1

print(rlt)

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

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

rlt = 0

for i in range(M):
  uf = UnionFind(N+1)
  for j in range(M):
    if i == j:
      continue
    e = edges[j]
    uf.union(e[0],e[1])
  if min(uf.parents) > -N:
    rlt += 1
    
print(rlt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ
 
    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]
 
    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]




def bridge(edges,v,e):#与えられるグラフが連結の場合
    hashi=[]#橋
    for i in range(e):
        uf=UnionFind(v)
        for j in range(e):
            if i==j:
                continue
            a,b=edges[j]
            uf.unite(a,b)
        if uf.group_size(0)!=v:#非連結でないなら頂点数と一致する
            hashi.append(i)
    return hashi

def is_bridge(edges,v,e,i):#0-indexのi番目の辺が橋か判定する
    uf=UnionFind(v)
    for j in range(e):
        if i==j:
            continue
        a,b=edges[j]
        uf.unite(a,b)
    if uf.group_size(0)!=v:
        return True
    else:
        return False

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

ans=0
for i in range(m):
    if is_bridge(edges,n,m,i):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ
 
    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]
 
    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]




def bridge(edges,v,e):#与えられるグラフが連結の場合
    hashi=[]#橋
    for i in range(e):
        uf=UnionFind(v)
        for j in range(e):
            if i==j:
                continue
            a,b=edges[j]
            uf.unite(a,b)
        if uf.group_size(0)!=v:#非連結でないなら頂点数と一致する
            hashi.append(edges[i])
    return hashi

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

print(len(bridge(edges,n,m)))

Submission status: Accepted

Solution code:
def c_bridge_networkx():
    import networkx as nx
    N, M = [int(i) for i in input().split()]
    Edges = [tuple([int(i) for i in input().split()]) for j in range(M)]

    graph = nx.Graph()
    graph.add_nodes_from(range(1, N + 1))
    graph.add_edges_from(Edges)
    # bridges(graph): graph の橋になる辺を結ぶ頂点の組を返す
    return len(tuple(nx.bridges(graph)))

print(c_bridge_networkx())

Submission status: Accepted

Solution code:
import sys
import copy
sys.setrecursionlimit(10000)

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        par[rx] = ry

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


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

par = [i for i in range(n)]

a = [0] * m
b = [0] * m

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

ans = 0

for i in range(m):
    c = copy.deepcopy(a)
    d = copy.deepcopy(b)
    c = c[:i] + c[i+1:]
    d = d[:i] + d[i+1:]
    par = [i for i in range(n)]
    for j in range(m-1):
        unite(c[j]-1, d[j]-1)
    if not same(a[i]-1, b[i]-1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

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

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

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

ans = 0
for i in range(M):
    u = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        a, b = es[j]
        u.unite(a, b)
    if u.get_size(0) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):                                          # 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):                                      # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)                                        # xをxの根に置き換える
        y = self.find(y)                                        # yをyの根に置き換える

        if x == y:                                              # 根が同じなら置き換える必要なし
            return

        if self.parents[x] > self.parents[y]:                   # 子がたくさんある方を x とする（出来るだけ浅い木にするため）
            x, y = y, x

        self.parents[x] += self.parents[y]                      # xの子の数を更新
        self.parents[y] = x                                     # yの親を更新

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

    def size(self, x):                                          # xの根のparent（= 要素数）を返す
        return -self.parents[self.find(x)]

    def members(self, x):                                       # xが属するグループの要素をリストとして返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):                                      # グループの数を返す
        return len(self.roots())

    def all_group_members(self):                                # {根:[根の子のリスト],...}を辞書で返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):                                          # print(self) での返し方を定義
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

data = [tuple(map(int, input().split())) for _ in range(M)]
res = 0

for k in range(M):
    tree = UnionFind(N)
    for a, b in data[:k] + data[k+1:]:
        a -= 1
        b -= 1
        tree.union(a,b)
    if tree.group_count() > 1:
       res += 1
print(res)

Submission status: Accepted

Solution code:
import networkx as nx

N, M = map(int, input().split())
G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
G.add_edges_from([tuple(map(int, input().split())) for _ in range(M)])

print(len(tuple(nx.bridges(G))))

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 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 i in range(m):
    a, b = map(int, input().split())
    edge.append((a - 1, b - 1))

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        uf.union(edge[j][0], edge[j][1])
    if uf.group_count() != 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def find(x):#xの親を見つける
  if par[x] < 0:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def unite(x,y):#要素xとｙを併合させる
  x,y=find(x),find(y)#xとyの親の検索
  if x!=y:#親が異なる場合併合させる
    if x>y:
        x,y=y,x#小さい方をxとする. これにより要素の値が小さいものを優先して木の根とする. 
    par[x]+=par[y] #値を無向木の要素数の和にする.
    par[y]=x #枝側は根の位置を格納

def same(x, y):#要素xと要素yが同じ無向木に所属しているかを判定する
  return find(x) == find(y)#同じ値を持つか否か

def size(x):#要素xが所属する無向木の大きさを返す
  return-par[find(x)]

N, M = map(int, input().split())
par = [-1] * N
def shokika():
  for i in range(N):
    par[i] = -1
    
def main():
  edge = []
  for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge.append([a, b])
  ans = 0
  for i in range(M):
    shokika()
    for j in range(M):
      if i == j:continue
      else:
        unite(edge[j][0], edge[j][1])
    top =  find(0)
    for j in range(1, N):
      if top != find(j):
        ans += 1
        break
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque
N, M = map(int, input().split())
adj_mat = [[-float('inf') for i in range(N)] for j in range(N)]
ls = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    ls.append([a, b])
    adj_mat[a][b], adj_mat[b][a] = 1, 1

ans = 0
for i in range(M):
    adj_mat_copy = deepcopy(adj_mat)
    adj_mat_copy[ls[i][0]][ls[i][1]] = -float('inf')
    adj_mat_copy[ls[i][1]][ls[i][0]] = -float('inf')
    st = deque([])
    visited = [-1 for i in range(N)]
    st.append(0)
    visited[0] = 1
    while st:
        l = st.pop()
        for j, node in enumerate(adj_mat_copy[l]):
            if node == 1 and visited[j] != 1:
                st.append(j)
                visited[j] = 1
    if sum(visited) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edges=[list(map(int,input().split())) for i in range(M)]
ans=0
for x in edges:
    l=list(range(N))
    for y in edges:
        if y!=x:l=[l[y[0]-1] if l[i]==l[y[1]-1] else l[i] for i in range(N)]
    if len(set(l))!=1:ans+=1
print(ans)

Submission status: Accepted

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

def dfs(u, seen, e):
    seen[u] = True
    for v in G[u]:
        if seen[v] == True:
            continue
        if [u, v] == e or [v, u] == e:
            continue
        dfs(v, seen, e)

ans = 0
for e in edges:
    seen = [False] * N
    dfs(e[0], seen, e)
    if seen[e[1]] == False:
        ans += 1

print(ans)

Submission status: Accepted

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

edges = []

for _ in range(m):
  edges.append(tuple(map(int,input().split())))

ans = 0
for i in range(m):
  g = [[] for _ in range(n)]
  for j,e in enumerate(edges):
    if i==j:
      continue
    a,b = e
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)
    
  checked = [False]*n
  queue = deque([0])
  while(len(queue)>0):
    q = queue.popleft()
    if checked[q]:
      continue
    checked[q] = True
    for p in g[q]:
      queue.append(p)
  if not all(checked):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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 = [[] for _ in range(N)]
    for j in range(M):
        if i==j:
            continue
        a, b = E[j]
        G[a].append(b)
        G[b].append(a)


    que = deque([0])

    check = [-1 for _ in range(N)]

    while que:
        v = que.popleft()
        check[v] = 0
        for i in G[v]:
            if check[i] == -1:
                que.append(i)
    if sum(check) < 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
l=[[] for _ in range(n)]
edge=[]
ans=0
for _ in range(m):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  edge.append([a-1,b-1])
for i,j in edge:
  q=deque([i])
  visited=[0]*n
  while q:
    x=q.pop()
    if x==j:
      break
    visited[x]=1
    for k in l[x]:
      if visited[k]==0 and not (x==i and k==j):
        q.append(k)
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
ab = [LI() for i in range(M)]

class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  # 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):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x

ans = 0
for i in range(M):
    a,b = ab[i]
    unionfind = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        else:
            unionfind.unite(ab[j][0],ab[j][1])
    if not unionfind.same_check(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())
ab = [list(map(int,input().split())) for _ in range(M)]
r = 0

for z in range(M):
  uf = UnionFind(N)
  for i in range(M):
    if z == i:
      continue
    uf.union(ab[i][0]-1,ab[i][1]-1)
  r += uf.group_count()-1

print(r)

Submission status: Accepted

Solution code:

def solve(pos):
  for i in range(n):
    if line[pos][i] == 1 and reach[i] == 0:
      reach[i] = 1
      solve(i)
  return

n, m = list(map(int, input().split()))
line = [[0]*n for i in range(n)]
ms = []

for i in range(m):
  a, b = list(map(int, input().split()))
  line[a-1][b-1]=1
  line[b-1][a-1]=1
  ms.append([a, b])
  
ans = 0
for i in range(m):
  line[ms[i][0]-1][ms[i][1]-1]=0
  line[ms[i][1]-1][ms[i][0]-1]=0
  reach=[0]*n
  reach[0]=1
  solve(0)
  if 0 in reach:
    ans += 1
  line[ms[i][0]-1][ms[i][1]-1]=1
  line[ms[i][1]-1][ms[i][0]-1]=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy

n, m = map(int, input().split())
arr = [[False] * 60 for x in range(60)]
ab = []

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


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


connected = [True] * m
for i in range(m):
    graph = copy.deepcopy(arr)
    graph[ab[i][0]][ab[i][1]] = False
    graph[ab[i][1]][ab[i][0]] = False
    visited = [False] * 60
    dfs(0)

    for j in range(n):
        if not visited[j]:
            connected[i] = False
            break


print(m - sum(connected))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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 main():
    N, M = map(int, readline().split())
    AB = [[int(s) - 1 for s in line.split()] for line in readlines()]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque

inf = 10**18
mod = 10**9+7

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
edge = [[]for k in range(n)]
for i in range(m):
    a,b = ab[i]
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = 0
for i in range(m): # i番目の編を無視したらどうなるか
    s,g = ab[i]
    s-=1
    g-=1
    visited = [False for j in range(n)]
    q = deque([s])
    while q:
        now = q.popleft()
        visited[now]=True
        for nn in edge[now]:
            if (now!=s or nn!=g) and (not visited[nn]):
                q.append(nn)
    if not all(visited):
        ans += 1
print(ans)

Submission status: Accepted

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

def dfs(pos):
  if visit[pos] == 1:
    return
  visit[pos] = 1
  
  for i in range(n):
    if graph[pos][i] == 1:
      dfs(i)

count = 0
for hen in range(m):
  graph = [[0]*n for i in range(n)]
  visit = [0]*n

  for i in range(m):
    pos1 = data[i][0] - 1
    pos2 = data[i][1] - 1
    if i != hen:
      graph[pos1][pos2] = 1
      graph[pos2][pos1] = 1
  dfs(0)
  connected = True
  for i in range(n):
    if visit[i] == 0:
      connected = False
  if not connected:
    count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
d = {i: [] for i in range(1, n+1)}
for a, b in L:
    d[a].append(b)
    d[b].append(a)
cnt = 0
for a, b in L:
    d[a].remove(b)
    d[b].remove(a)
    ds = {i: -1 for i in range(1, n+1)}
    ds[1] = 0
    q = deque([1])
    while q:
        t = q.popleft()
        for v in d[t]:
            if ds[v] < 0:
                ds[v] += 1
                q.append(v)
    if -1 in ds.values():
        cnt += 1
    d[a].append(b)
    d[b].append(a)
print(cnt)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 8)


def lowLink(N: int, Adj: list):
	articulation = []
	bridge = []
	order = [None] * N
	lowest = [1 << 100] * N

	def _dfs(cur, pre, k):
		order[cur] = lowest[cur] = k
		is_articulation = False
		cnt = 0
		for nxt in Adj[cur]:
			if order[nxt] is None:
				cnt += 1
				_dfs(nxt, cur, k + 1)
				if lowest[cur] > lowest[nxt]:
					lowest[cur] = lowest[nxt]
				is_articulation |= pre >= 0 and lowest[nxt] >= order[cur]
				if order[cur] < lowest[nxt]:
					if cur < nxt:
						bridge.append((cur, nxt))
					else:
						bridge.append((nxt, cur))
			elif nxt != pre and lowest[cur] > order[nxt]:
				lowest[cur] = order[nxt]
		is_articulation |= pre < 0 and cnt > 1
		if is_articulation:
			articulation.append(cur)

	"""
	kk = 0
	for i in range(N):
		if order[i] is None:
			kk = _dfs(i, -1, kk)
	"""
	_dfs(0, -1, 0)
	return articulation, bridge

def main():
	n,m,*L=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	for a,b in zip(*[iter(L)]*2):
		con[a-1].append(b-1)
		con[b-1].append(a-1)
	_,br=lowLink(n,con)
	print(len(br))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
data = [[] for _ in range(n)]
hen = []
ans = 0
for _ in range(m):
    v,w = map(int,input().split())
    v -= 1
    w -= 1
    data[v].append(w)
    data[w].append(v)
    hen.append((v,w))
for i,j in hen:
    dq = deque([i])
    visited = [0]*n
    while dq:
        p = dq.pop()
        if p == j:
            break
        visited[p] = 1
        for k in data[p]:
            if (not visited[k]) and (not (p == i and k == j)):
                dq.append(k)
    else:
        ans += 1
print(ans)