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:
#!/usr/bin/env python3
import sys

# refered to
# rank : http://at274.hatenablog.com/entry/2018/02/02/173000
# size : abc120 kaisetsu
class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # もう繋がれている
        if(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True 


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if(j == i):
                continue
            else:
                uf.union(a[j], b[j])

        if(not uf.same_check(a[i], b[i])):
            ans += 1
        
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self, N):
        self.size = N
        self.par = [None] * N
        self.rank = [None] * N
        for n in range(N):
            self.par[n] = n
            self.rank[n] = 1

    def root(self, x):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.size -= 1
            if self.rank[rx] > self.rank[ry]:
                self.par[ry] = rx
            else:
                self.par[rx] = ry
                if self.rank[rx] == self.rank[ry]:
                    self.rank[ry] += 1

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

c = 0
for i in range(M):
    # i 番目の辺を採用しない場合にグラフが連結かどうか？
    uf = UnionFind(N)
    for a, b in ab[0:i]+ab[i+1:M]:
        uf.unite(a-1, b-1)
    if uf.size > 1:
        c += 1
print(c)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*(n)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    

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

for i in range(M):
    uf = UnionFind(N+1)
    for j in range(M):
        if j == i:
            continue
        else:
            uf.union(edge[j][0], edge[j][1])
    
    if not uf.same_check(edge[i][0], edge[i][1]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N , M = map(int,input().split()) 
ab = [list(map(int,input().split())) for _ in range(M)]
flg = True
ch = [0] * N
gl = [[0] * N for _ in range(N)] 
# 隣接行列を作成する
for x in ab:
    gl[x[0]-1][x[1]-1] = 1
    gl[x[1]-1][x[0]-1] = 1
# パスが１つしかない頂点のパスは橋である
# 橋と橋以外のパスが１本しかない頂点の橋以外のパスも橋である
# 隣接行列を更新しながら各頂点についてチェックを繰り返せばよい
count = 0
while flg:
    flg = False
    for i in range(N):
        if (ch[i] == 0 )and (sum(gl[i]) == 1):
            ch[i] = 1
            count += 1
            flg = True
            for j in range(N):
                if gl[i][j] == 1:
                    gl[j][i] = 0
print(count)

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
vertex=[[int(i) for i in l.split()] for l in sys.stdin]
def find(x):
  if root[x]==x:
    return x
  root[x]=find(root[x])
  return root[x]
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  x=find(x)
  y=find(y)
  if size[x]>=size[y]:
    root[y]=x
  else:
    root[x]=y
  if size[x]==size[y]:
    size[x]+=1
ans=0
for i in range(m):
  root=[i for i in range(n+1)]
  size=[0]*(n+1)
  for j in range(m):
    if j!=i:
      if check(vertex[j][0],vertex[j][1]):
        pass
      else:
        union(vertex[j][0],vertex[j][1])
  for j in range(1,n):
    if check(j,j+1)==True:
      pass
    else:
      ans+=1
      break
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
l = [[0]*n for _ in range(n)]
for a_ in a:
    l[a_[0]-1][a_[1]-1] = 1
    l[a_[1]-1][a_[0]-1] = 1
visited = [False]*n
def dfs(v):
    visited[v] = True
    for i in range(n):
        if l[v][i]==1 and not visited[i]:
            dfs(i)
    return visited
ans = 0
for a_ in a:
    l[a_[0]-1][a_[1]-1] = 0
    l[a_[1]-1][a_[0]-1] = 0
    bridge = False
    k = dfs(0)
    for i in k:
        if not i:
            bridge=True
    if bridge:
        ans += 1
    visited = [False]*n
    l[a_[0]-1][a_[1]-1] = 1
    l[a_[1]-1][a_[0]-1] = 1
print(ans)

Submission status: Accepted

Solution code:
n,m=[int(val) for val in input().split()]
matrix=[[int(val) for val in input().split()]for val in range(m)]
#print(n,m,matrix)
ee=[[val[0]-1, val[1]-1] for val in matrix]

cnt=0
k=0
for L in range(m):
    xx=[i for i in range(n)]
    for j in range(m):
        if j!=k:
            val1=xx[ee[j][1]]
            val2=xx[ee[j][0]]
            for i in range(len(xx)):
                if xx[i]==val1:
                    xx[i]=val2
#    print(xx)
    if len(set(xx))>1:
        cnt+=1
    k+=1
    
print(cnt)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split(' ')]

edges = [(input().split(' ')) for _ in range(m)]
ans = 0


def bfs(bridge):
    queue = ['1']
    visited = set()
    while queue:
        node = queue.pop()
        visited.add(node)
        next_nodes = [
            x[1] for x in edges if x[0]==node and x[1] not in visited and bridge!=x
        ] + [
            x[0] for x in edges if x[1]==node and x[0] not in visited and bridge!=x
        ]
        queue.extend(next_nodes)
        if len(visited) == n:
            return False
    return True


for edge in edges:
    if bfs(edge):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
branch=[tuple(map(int,input().split())) for i in range(M)]
def check(x):
    data=defaultdict(set)
    for i in range(M):
        if i==x:continue
        a,b=branch[i]
        data[a]|={b,}
        data[b]|={a,}
    if len(data[1])==0:
        return False
    visited={1,}
    check={1,}
    while len(check)>0:
        now=check.pop()
        for nex in data[now]:
            if nex not in visited:
                visited|={nex,}
                check|={nex,}
    if len(visited)==N:return True
    return False
cnt=0
for i in range(M):
    if not check(i):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
flg = 1
ans = 0
a = [list(map(int, input().split())) for _ in range(M)]
while flg == 1:
    d = defaultdict(int)
    flg = 0
    for link in a:
        d[link[0]] += 1
        d[link[1]] += 1
    for node in range(1, M + 1):
        if d[node] == 1:
            ans += 1
            flg = 1
            a = [x for x in a if node not in x]
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
a=[]
b=[]
G =[[] for _ in range(N)] #連結リスト
for i in range(M):
    ai,bi = map(int,input().split())
    ai -= 1
    bi -= 1
    G[ai].append(bi)
    G[bi].append(ai)
    a.append(ai)
    b.append(bi)
used = [0]*(N)
#幅優先探索で連結判定
def dfs(v):
    used[v] = True
    for u in G[v]:
        if demo1==v and demo2==u:
            continue
        if not used[u]:
            dfs(u)
    return
demo1=0
demo2=0
ans = 0
#各辺についてそれが橋かどうかチェック
for i in range(M):
    for j in range(N):
        used[j] = False
    demo1=a[i]
    demo2=b[i]
    dfs(a[i])
    if not used[b[i]]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

def f(a, D):
    N = len(D)
    p = []
    for i in range(N):
        if D[a][i] == 1:
            p.append(i)
    return p


def wfs(e, D):
    N = len(D)
    a, b = e[0], e[1]

    p = f(a, D)
    used = [a]
    while len(p) > 0:
        x = p.pop(0)
        used.append(x)

        if x == b:
            return True

        q = f(x, D)
        for j in q:
            if j in used:
                continue
            p.append(j)

    return False


def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = []
    for _ in range(M):
        a, b = map(int, input().split())
        G.append((a-1, b-1))

    ans = 0
    for i in range(M):
        D = [[0 for _ in range(N)] for _ in range(N)]
        for j in range(M):
            if j == i:
                continue

            a, b = G[j][0], G[j][1]
            D[a][b] = 1
            D[b][a] = 1

        if not wfs(G[i], D):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=[int(val) for val in input().split()]
matrix=[[int(val) for val in input().split()]for val in range(m)]
#print(n,m,matrix)
ee=[[val[0]-1, val[1]-1] for val in matrix]

cnt=0
k=0
for L in range(m):
    xx=[i for i in range(n)]
    for j in range(m):
        if j!=k:
            val1=xx[ee[j][1]]
            val2=xx[ee[j][0]]
            for i in range(len(xx)):
                if xx[i]==val1:
                    xx[i]=val2
#    print(xx)
    if len(set(xx))>1:
        cnt+=1
    k+=1
    
print(cnt)

Submission status: Accepted

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

ans = 0
pre = [-1]*n
low = [-1]*n

def dfs(v,p,a):
	global ans
	if pre[v] != -1:
		low[a] = min(low[a],low[v])
		return low[a]
	pre[v] = p
	low[v] = p
	for u in links[v]:
		if u == a:
			continue
		low[v] = min(low[v],dfs(u,p+1,v))
	if pre[v] == low[v]:
		ans += 1
	return low[v]

dfs(0,0,None)
print(ans-1)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    self.n   = num
    self.size = [1]*num

#親を探す
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x]) #自分じゃなきゃ親を探す
      return self.par[x]

#集合を結合する(結合する前に親のポインタを取得する)
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] > self.rank[y]: #ランクの高い方に基準を合わせる
      self.par[y] = x
      self.size[x]+=self.size[y]
      self.size[y] = 0
    else:
      self.par[x] = y
      self.size[y] += self.size[x]
      self.size[x] = 0
      if self.rank[x] == self.rank[y]:
        self.rank[y] += 1

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

  def all_find(self):
    ls=[]
    for i in range(len(self.par)):
      ls.append(self.find(i))
    return ls

n,m=map(int,input().split())
edges=[[0]*n for i in range(n)]
AB=[]
ans=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  AB.append([a-1,b-1])
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
  ans.union(a-1,b-1)
cnt=0
for i in range(m):
  uf=UnionFind(n)
  for j in range(m):
    if i==j:
      continue
    a,b=AB[j]
    uf.union(a,b)
  if len(set(uf.all_find()))>1:
    cnt+=1
print(cnt)

Submission status: Accepted

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

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

for i in range(M):
    ai, bi = map(lambda x: int(x) - 1, input().split())
    graph[ai].append(bi)
    graph[bi].append(ai)

low = [N] * N
rank = [N] * N
visited = [False] * N


def dfs(k, pos, parent):
    low[pos] = k
    rank[pos] = k

    k += 1

    visited[pos] = True

    for i in graph[pos]:
        if not visited[i]:
            k = dfs(k, i, pos)
            low[pos] = min(low[pos], low[i])
        elif i != parent:
            low[pos] = min(low[pos], low[i])

    return k


def main():
    dfs(0, 0, -1)

    print(sum(
        [1 for i in range(N) for j in graph[i] if rank[j] < low[i]]))

    return


main()

Submission status: Accepted

Solution code:


def dfs(graph: list,
        v: int,
        _from: int,
        low: list,
        pre: list,
        ret: list,
        count: list)->int:
    pre[v] = count[0]
    low[v] = count[0]

    count[0] += 1

    for to in graph[v]:
        if pre[to] >= 0:
            # already visited
            if _from != to:
                low[v] = min(low[v], low[to])
        else:
            low[v] = min(low[v], dfs(graph, to, v, low, pre, ret, count))
            if low[to] == pre[to]:
                ret.append((v, to))

    return low[v]


def bridge(N: int, M: int, edges: list)->int:
    graph = [[] for _ in range(N)]
    for u, v in edges:
        graph[u-1].append(v-1)
        graph[v-1].append(u-1)

    low, pre = [-1] * N, [-1] * N
    ret = []
    dfs(graph, 0, -1, low, pre, ret, [0])

    return len(ret)


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = bridge(N, M, edges)
    print(ans)

Submission status: Accepted

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

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

for i in range(M):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    graph[ai].append(bi)
    graph[bi].append(ai)

rank = [N] * N
low = [N] * N
visited = [False] * N


def dfs(k, pos, parent):
    rank[pos] = k
    low[pos] = k

    k += 1

    visited[pos] = True

    for i in graph[pos]:
        if not visited[i]:
            k = dfs(k, i, pos)
            low[pos] = min(low[pos], low[i])
        elif i != parent:
            low[pos] = min(low[pos], low[i])

    return k


def main():
    dfs(0, 0, -1)

    ans = 0

    for i in range(N):
        for j in graph[i]:
            if rank[j] < low[i]:
                ans += 1

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split()))for i in range(m)]
b=[[]for i in range(n)]
for i in range(m):
    b[a[i][0]-1]+=[a[i][1]-1]
    b[a[i][1]-1]+=[a[i][0]-1]
def f(x,p,q):
    c[x]=True
    for i in b[x]:
        if c[i]==False:
            if (i==p and x==q) or(i==q and x==p):
                continue
            else:
                f(i,p,q)
d=0
for i in range(m):
    c=[False]*n
    f(a[i][0]-1,a[i][0]-1,a[i][1]-1)
    if c!=[True]*n:
        d+=1
print(d)

Submission status: Accepted

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

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

for i in range(M):
    ai, bi = map(int, input().split())
    ai -= 1
    bi -= 1
    graph[ai].append(bi)
    graph[bi].append(ai)

rank = [N] * N
low = [N] * N
visited = [False] * N


def dfs(k, pos, parent):
    rank[pos] = k
    low[pos] = k

    k += 1

    visited[pos] = True

    for i in graph[pos]:
        if not visited[i]:
            dfs(k, i, pos)
            low[pos] = min(low[pos], low[i])
        elif i != parent:
            low[pos] = min(low[pos], rank[i])


def main():
    dfs(0, 0, -1)

    ans = 0

    for i in range(N):
        for j in graph[i]:
            if rank[j] < low[i]:
                ans += 1

    print(ans)
    return


main()

Submission status: Accepted

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

graph = [[False for j in range(N)] for i in range(N)]

am = [0] * M
bm = [0] * M


def dfs(visited, n):
    visited[n] = True

    for k, v in enumerate(visited):
        if v:
            continue

        if not graph[n][k]:
            continue

        visited = dfs(visited, k)

    return visited


def main():
    for i in range(M):
        # 0-indexed
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        am[i] = ai
        bm[i] = bi

        graph[ai][bi] = True
        graph[bi][ai] = True

    ans = 0

    for ai, bi in zip(am, bm):
        graph[ai][bi] = False
        graph[bi][ai] = False

        # 訪問済 All False
        visited = dfs([False] * N, 0)

        # All True ならば 橋 ではない
        if not all(visited):
            ans += 1

        # 元に戻す
        graph[ai][bi] = True
        graph[bi][ai] = True

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
# union findでの実装
class UnionFind:
    # 親要素のノード番号を格納。par[x] == xの時そのノードは根
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    
    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x]==x:
            return x
        # 根でないなら親の要素で再検索、走査していく過程で親を書き換える
        else:
            self.par[x] =  self.find(self.par[x])
            return self.par[x]
    
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x)==self.find(y)
    
    #  併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低い方から高い方へ辺を貼る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        # 木の高さが同じなら片方を1増やす
            if self.rank[x]==self.rank[y]:
                self.rank[x] += 1

                
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
ans = 0
for i in range(M):
    graph = UnionFind(N)
    for edge in edges:
        if edge==edges[i]:
            continue
        else:
            graph.union(*edge)
    par = [graph.par[i+1]==i+1 for i in range(N)]
    if par.count(True)==1:
        continue
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def judge(visited):
    for v in visited:
        if not v:
            return True
    else:
        # 完走 橋ではない
        return False


def main():
    def dfs(visited, n):
        visited[n] = True

        for k, v in enumerate(graph[n]):
            if not v:
                continue

            if visited[k]:
                continue

            visited = dfs(visited, k)

        return visited

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

    graph = [[False for j in range(N)] for i in range(N)]

    am = [0] * M
    bm = [0] * M

    for i in range(M):
        # 0-indexed
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        am[i] = ai
        bm[i] = bi

        graph[ai][bi] = True
        graph[bi][ai] = True

    ans = 0

    for ai, bi in zip(am, bm):
        graph[ai][bi] = False
        graph[bi][ai] = False

        # 訪問済 All False
        if judge(dfs([False] * N, 0)):
            ans += 1

        # 元に戻す
        graph[ai][bi] = True
        graph[bi][ai] = True

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
def judge(visited):
    for v in visited:
        if not v:
            return True
    else:
        # 完走 橋ではない
        return False


def dfs(visited, graph, n):
    visited[n] = True

    for k, v in enumerate(graph[n]):
        if not v:
            continue

        if visited[k]:
            continue

        visited = dfs(visited, graph, k)

    return visited


def main():
    N, M = map(int, input().split())

    graph = [[False for j in range(N)] for i in range(N)]

    am = [0] * M
    bm = [0] * M

    for i in range(M):
        # 0-indexed
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        am[i] = ai
        bm[i] = bi

        graph[ai][bi] = True
        graph[bi][ai] = True

    ans = 0

    for ai, bi in zip(am, bm):
        graph[ai][bi] = False
        graph[bi][ai] = False

        # 訪問済 All False
        visited = dfs([False] * N, graph, 0)

        if judge(visited):
            ans += 1

        # 元に戻す
        graph[ai][bi] = True
        graph[bi][ai] = True

    print(ans)
    return


main()

Submission status: Accepted

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

graph = [[False for j in range(N)] for i in range(N)]

am = [0] * M
bm = [0] * M


def judge(visited):
    for v in visited:
        if not v:
            return True
    else:
        # 完走 橋ではない
        return False


def dfs(visited, n):
    visited[n] = True

    for k, v in enumerate(graph[n]):
        if not v:
            continue

        if visited[k]:
            continue

        visited = dfs(visited, k)

    return visited


def main():
    for i in range(M):
        # 0-indexed
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        am[i] = ai
        bm[i] = bi

        graph[ai][bi] = True
        graph[bi][ai] = True

    ans = 0

    for ai, bi in zip(am, bm):
        graph[ai][bi] = False
        graph[bi][ai] = False

        # 訪問済 All False
        visited = dfs([False] * N, 0)

        if judge(visited):
            ans += 1

        # 元に戻す
        graph[ai][bi] = True
        graph[bi][ai] = True

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
# 隣接行列知らないと書けない、あるいは隣接リスト, BFS, union find
# まずは隣接リストでdfs、グローバル変数どうする？
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

def dfs(v):
    # 連結かどうか確かめる
    visited[v] = True
    for v2 in con_list[v]:
        if visited[v2] == True: continue
        else: dfs(v2)

ans = 0
for i in range(M):
    graph = AB[:i] + AB[i+1:]
    # 隣接リスト: 0~N-1に置き換え
    con_list = [[] for _ in range(N)]
    for edge in graph:
        con_list[edge[0]-1].append(edge[1]-1)
        con_list[edge[1]-1].append(edge[0]-1)
    # global visited
    visited = [False] * N
    dfs(0)
    if not all(visited):
        ans += 1
print(ans)

Submission status: Accepted

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

graph = [[False for j in range(N)] for i in range(N)]

am = [0] * M
bm = [0] * M


def judge(visited):
    for v in visited:
        if not v:
            return True
    else:
        # 完走 橋ではない
        return False


def dfs(visited, n):
    visited[n] = True

    for k, v in enumerate(visited):
        if v:
            continue

        if not graph[n][k]:
            continue

        visited = dfs(visited, k)

    return visited


def main():
    for i in range(M):
        # 0-indexed
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        am[i] = ai
        bm[i] = bi

        graph[ai][bi] = True
        graph[bi][ai] = True

    ans = 0

    for ai, bi in zip(am, bm):
        graph[ai][bi] = False
        graph[bi][ai] = False

        # 訪問済 All False
        visited = dfs([False] * N, 0)

        if judge(visited):
            ans += 1

        # 元に戻す
        graph[ai][bi] = True
        graph[bi][ai] = True

    print(ans)
    return


main()

Submission status: Accepted

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


class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)
        self._number = [1] * (N + 1)

    def root(self, i):
        if self.par[i] == i:
            return i
        self.par[i] = self.root(self.par[i])
        return self.par[i]

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def tree_rank(self, i):
        return self.rank[self.root(i)]

    def number(self, i):
        return self._number[self.root(i)]

    def union(self, i, j):
        _root_i = self.root(i)
        _root_j = self.root(j)
        if _root_i == _root_j:
            return
        else:
            if self.tree_rank(i) < self.tree_rank(j):
                self.par[_root_i] = _root_j
                self._number[_root_j] += self._number[_root_i]
            else:
                self.par[_root_j] = _root_i
                self._number[_root_i] += self._number[_root_j]
                if self.tree_rank(i) == self.tree_rank(j):
                    self.rank[_root_i] += 1


def whether_graph_connected(n, link):
    _islands = UnionFind(n)
    for l in link:
        _islands.union(l[0], l[1])
    return _islands.number(_islands.root(1)) == n

  
count = 0

for bridge_broken in bridge:
    bridge_remain = [_ for _ in bridge if _ != bridge_broken]
    if not whether_graph_connected(N, bridge_remain):
        count += 1

print(count)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # もう繋がれている
        if(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True 

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    
    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(not uf.same_check(a[i],b[i])):
            ans += 1
    print(ans)
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n,m = map(int, input().split())
dic = dd(list)
l = []
cnt = 0
for _ in range(m):
  a,b = map(int, input().split())
  l.append((a,b))
  dic[a].append(b)
  dic[b].append(a)
def con(x):
  visit.add(x)
  for i in dic[x]:
    if i in visit:
      continue
    con(i)
  return visit == set(range(1,n+1))
for x,y in l:
  dic[x].remove(y)
  dic[y].remove(x)
  visit = set()
  if not con(x):
    cnt += 1
  dic[x].append(y)
  dic[y].append(x)
print(cnt)

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.table[xp] < self.table[yp]:
                self.table[xp] += self.table[yp]
                self.table[yp] = xp
            else:
                self.table[yp] += self.table[xp]
                self.table[xp] = yp

n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
ret = 0
for i in range(m):
    uni = Unionfind(n)
    for j in range(m):
        if j != i:
            uni.union(edge[j][0] - 1, edge[j][1] - 1)
    for j in range(n):
        if uni.table[j] < 0 and -(uni.table[j]) != n:
            ret += 1
            break
print(ret)

Submission status: Accepted

Solution code:
import copy
from collections import deque

def dfs(E):
    connected = []
    connected.append(1)
    S = deque([])
    S.append(1)
    while len(S):
        v = S.pop()
        for vv in E[v-1]:
            if vv not in connected:
                connected.append(vv)
                S.append(vv)
    
    return len(connected)


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

count = 0
for i in range(M):
    E2 = copy.deepcopy(E)
    a, b = bridge[i]
    E2[a-1].remove(b)
    E2[b-1].remove(a)
    if dfs(E2) != N:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import copy
n, m = (int(i) for i in input().split())
e = [[int(i)-1 for i in input().split()] for i in range(m)]

b = arr = [[0 for i in range(n)] for j in range(n)]

for x in e:
    b[x[0]][x[1]] = 1
    b[x[1]][x[0]] = 1

def f(idx):
    used[idx] = 1
    for i in range(n):
        if b_[idx][i] == 1 and used[i] == 0:
            f(i)

count = 0
for x in e:
    b_ = copy.deepcopy(b)
    b_[x[0]][x[1]] = 0
    b_[x[1]][x[0]] = 0
    used = [0]*n
    f(0)
    if used.count(1) != n:
        count+=1

print(count)