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())
graph = [[0]*N for _ in range(N)]
Edge = []

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

def dfs(x):
  if(vis[x] == 1): return
  vis[x] = 1
  for i in range(N):
    if(graph[x][i] == 1):
      dfs(i)

ans = 0      
for i in range(M):
  graph[Edge[i][0]][Edge[i][1]] = 0
  graph[Edge[i][1]][Edge[i][0]] = 0
  vis = [0]*60
  dfs(0)
  for j in range(N):
    if(vis[j] == 0):
      ans += 1
      break
  graph[Edge[i][0]][Edge[i][1]] = 1
  graph[Edge[i][1]][Edge[i][0]] = 1
print(ans)

Submission status: Accepted

Solution code:
import copy

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

neighbor = [[0]*N for _ in range(N)]
edge = []

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

# visitリストを更新する関数。初期化したvisitedを用意した上で呼び出す
def visit_points(current_point):
    visited[current_point] = 1
    neighbor_point = [x for x in range(len(tmp_neighbor[current_point])) if tmp_neighbor[current_point][x] > 0]
    for np in neighbor_point:
        if visited[np] == 0:
            visit_points(np)

# 辺を1つ削除した後に、DFSで連結かどうか調べる
n_bridge = 0

for idx in range(M):
    tmp_neighbor = copy.deepcopy(neighbor)
    tmp_neighbor[edge[idx][0]][edge[idx][1]] = 0
    tmp_neighbor[edge[idx][1]][edge[idx][0]] = 0

    visited = [0]*N
    visit_points(0)
    if sum(visited) < N:
        n_bridge += 1

print(n_bridge)

Submission status: Accepted

Solution code:
from collections import deque

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

ans=0
for i in range(m):
    ll=l[:i]+l[i+1:]
    tree=[[] for i in range(n)]
    for i in ll:
        tree[i[0]-1].append(i[1]-1)
        tree[i[1]-1].append(i[0]-1)
    seen=[]
    seen.append(0)
    dq=deque()
    dq.append(0)
    cnt=1
    while dq:
        x=dq.pop()
        for i in tree[x]:
            if i not in seen:
                seen.append(i)
                dq.append(i)
                cnt+=1
    if cnt!=n:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())

graph = [set() for _ in range(N + 1)]
edge = []
##immutableに気をつけて
for m in range(M):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)
    edge.append([a, b])

ans = 0
for m in range(M):
    Bridge = True
    fr, to = edge[m][0], edge[m][1]
    V = {fr} | set(graph[fr]) - {to}
    que = deque(set(graph[fr]) - {to})
    while que:
        node = que.pop()
        for new_node in graph[node]:
            if new_node == to:
                Bridge = False
                break
            if new_node not in V:
                que.append(new_node)
                V.add(new_node)
        else:
            continue
        break
    if Bridge:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())

graph = [set() for _ in range(N + 1)]
edge = []
for m in range(M):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)
    edge.append([a, b])

ans = 0
for m in range(M):
    Bridge = True
    fr, to = edge[m][0], edge[m][1]
    V = {fr} | set(graph[fr]) - {to}
    que = set(graph[fr]) - {to}
    while que:
        node = que.pop()
        for new_node in graph[node]:
            if new_node == to:
                Bridge = False
                break
            if new_node not in V:
                que.add(new_node)
                V.add(new_node)
        else:
            continue
        break
    if Bridge:
        ans += 1
print(ans)

Submission status: Accepted

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

graph = [[0] * N for _ in range(N)] #隣接行列
Edge = [] #辺
for i in range(M):
  a,b = map(int,input().split())
  graph[a-1][b-1] = 1
  graph[b-1][a-1] = 1
  Edge.append([a-1,b-1])
  
def dfs(x): #深さ優先探索 / visを変化させる関数
  if(vis[x] == 1): return
  vis[x] = 1
  for i in range(N):
    if(graph[x][i] == 1):
     dfs(i)

#(方針)「ある1辺を除く→グラフが非連結か（非連結ならその辺は橋）」ということを繰り返す    
ans = 0
for i in range(M):
 graph[Edge[i][0]][Edge[i][1]] = 0 #辺を除く
 graph[Edge[i][1]][Edge[i][0]] = 0 #辺を除く
 vis = [0]*60 #頂点を訪れたか
 dfs(0) #深さ優先探索
 for j in range(N): 
    if(vis[j] == 0): #訪れなかった頂点がある → グラフは非連結
     ans += 1 #非連結なら橋の数+1
     break
 graph[Edge[i][0]][Edge[i][1]] = 1 #辺を戻す 
 graph[Edge[i][1]][Edge[i][0]] = 1 #辺を戻す
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(m):
    ai, bi = map(int, input().split())
    ab.append([ai, bi])

def check_1(ab_lists):
    while True:
        if len(ab_lists) == 1:
            if len(ab_lists[0]) == n:
                return True
            else:
                return False
        if len(ab_lists) == 2 and len(ab_lists[0]) + len(ab_lists[1]) == len(set(ab_lists[0] + ab_lists[1])):
            return False
        for i in range(len(ab_lists)):
            flag = 0
            for j in range(i+1, len(ab_lists)):
                if len(ab_lists[i]) + len(ab_lists[j]) != len(set(ab_lists[i] + ab_lists[j])):
                    ab_lists[i] = list(set(ab_lists[i] + ab_lists[j]))
                    flag = 1
                    break
            if flag == 1:
                ab_lists.pop(j)
                break

res = 0
for i in range(m):
    ab_lists = ab[:i] + ab[i+1:]
    ret = check_1(ab_lists)
    if not ret:
        res += 1
print(res)

Submission status: Accepted

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

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

ans = 0
for _, e in enumerate(edge):
  graph[e[0]-1][e[1]-1] = False
  graph[e[1]-1][e[0]-1] = False

  for j in range(n):
    visited[j] = False

  dfs(0)

  bridge = False
  for j in range(n):
    if not all(visited):
      bridge = True
  if bridge:
    ans += 1

  graph[e[0]-1][e[1]-1] = True
  graph[e[1]-1][e[0]-1] = True

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
deg = [0]*n
seen = [False]*n
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
    deg[x-1] += 1
    deg[y-1] += 1
q = deque([i for i in range(n) if deg[i] == 1])
while q:
    v = q.popleft()
    seen[v] = True
    for i in graph[v]:
        deg[i] -= 1
        if deg[i] == 1:
            q.append(i)
if all(seen[i] == 1 for i in range(n)):print(n-1);exit()
print(seen.count(1))

Submission status: Accepted

Solution code:

# C
from collections import deque

def Connected(g, nodenum):
    visited = [False]*nodenum
    que = deque([])
    posi = 0
    que.append(posi)
    while que:
        visit = que.pop()
        visited[visit] = True
        for goto in g[visit]:
            if visited[goto]:
                continue
            que.append(goto)
    if all(visited):
        return True
    else:
        return False

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

ans = 0
for edge in edge_log:
    g[edge[0]].remove(edge[1])
    g[edge[1]].remove(edge[0])
    if not Connected(g, nodenum=n):
        ans += 1
    g[edge[0]].append(edge[1])
    g[edge[1]].append(edge[0])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m= map(int,input().split())
graph = [[]for _ in range(n)]
deg = [0 for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
    deg[x-1] += 1
    deg[y-1] += 1
q = deque([i for i in range(n) if deg[i] == 1])# 無向グラフのシンクは 1
seen = [False for _ in range(n)]

while q:
    v = q.popleft()
    seen[v] = True
    for i in graph[v]:
        deg[i] -= 1
        if deg[i] == 1:
            q.append(i)
if all(i for i in seen):print(n-1);exit()
print(seen.count(True))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
edge = [[0 for i in range(N)] for i in range(N)]
edges = [(0,0) for i in range(M)]
ckd = [False for i in range(N)]
ans = 0


for i in range(M):
  a, b = map(int, input().split())
  edge[a-1][b-1] = 1
  edge[b-1][a-1] = 1
  edges[i] = (a-1, b-1)
  
for e in edges:
  edge[e[0]][e[1]] = 0
  edge[e[1]][e[0]] = 0
  
  q = deque()
  q.append(0)
  ckd = [False for i in range(N)]
  
  while q:
    r = q.popleft()
    for d in range(N):
      if edge[r][d] and not(ckd[d]):
        ckd[d] = True
        q.append(d)
        
  if not(all (c for c in ckd)):
    ans += 1
    
  edge[e[0]][e[1]] = 1
  edge[e[1]][e[0]] = 1
  
print(ans)

Submission status: Accepted

Solution code:
# Union Find 木
def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


N, M = map(int, input().split())
ab = [[int(c) - 1 for c in input().split()] for _ in range(M)]

result = 0
for i in range(M):
    parent = [-1] * N
    for j in range(M):
        if j == i:
            continue
        unite(parent, ab[j][0], ab[j][1])
    if len([i for i in parent if i < 0]) != 1:
        result += 1
print(result)

Submission status: Accepted

Solution code:
class LowLink:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.used = [0] * n
        self.ord = [0] * n
        self.low = [0] * n
        self.bridge = []
        self.articulation = []

    def dfs(self, v, order, prev):
        order += 1
        self.used[v] = 1
        self.ord[v] = order
        self.low[v] = self.ord[v]

        is_articulation = False
        cnt = 0
        for to in self.adj[v]:
            if not self.used[to]:
                cnt += 1
                order = self.dfs(to, order, v)
                self.low[v] = min(self.low[v], self.low[to])
                if prev != -1:
                    is_articulation |= self.low[to] >= self.ord[v]
                if(self.ord[v] < self.low[to]):
                    if v < to:
                        self.bridge.append((v, to))
                    else:
                        self.bridge.append((to, v))
            elif to != prev:
                self.low[v] = min(self.low[v], self.low[to])
        if prev == -1:
            is_articulation |= cnt > 1
        if is_articulation:
            self.articulation.append(v)
        return order

    def build(self):
        order = 0
        for i in range(self.n):
            if not self.used[i]:
                order = self.dfs(i, order, -1)

if __name__ == "__main__":
    n, m = [int(item) for item in input().split()]
    edge = [[] for _ in range(n)]

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

    LL = LowLink(edge)
    LL.build()
    # print(LL.bridge)
    # print(LL.articulation)
    print(len(LL.bridge))

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 5)

N, M = map(int, input().split())
ab = [[int(c) - 1 for c in input().split()] for _ in range(M)]

result = 0
for i in range(M):
    parent = [-1] * N
    for j in range(M):
        if j == i:
            continue
        unite(parent, ab[j][0], ab[j][1])
    if len([i for i in parent if i < 0]) != 1:
        result += 1
print(result)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = []
T = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    T[a].add(b)
    T[b].add(a)
    E.append([a, b])

ans = 0
for i in range(M):
    s, t  = E[i][0], E[i][1]
    V, queue = set([s]) | T[s] - set([t]), T[s] - set([t])
    Bridge = True
    while len(queue) > 0:
        v = queue.pop()
        for u in T[v]:
            if u == t:
                Bridge = False
                break
            if u not in V:
                queue.add(u)
                V.add(u)
        else:
            continue
        break
    if Bridge:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

def make_dict(x,y):
    for i in ll:
        if i[x] in d.keys():
            d[i[x]]+=[i[y]]
        else:
            d[i[x]]=[i[y]]

cnt=0
for i in range(m):
    ll=l[:i]+l[i+1:]
    d={}
    make_dict(0,1)
    make_dict(1,0)
    k_l=list(d.keys())
    x=0
    sk=k_l[x]
    dq=deque()
    dq.append(sk)
    seen=[]
    while dq:
        k=dq.pop()
        k_ll=d[k]
        seen.append(k)
        for i in k_ll:
            if i not in seen:
                dq.append(i)
        x+=1
    if len(set(seen))!=n:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

def make_dict(x,y):
    for i in ll:
        if i[x] in d.keys():
            d[i[x]]+=[i[y]]
        else:
            d[i[x]]=[i[y]]

cnt=0
for i in range(m):
    ll=l[:i]+l[i+1:]
#    print(ll)
    d={}
    make_dict(0,1)
    make_dict(1,0)
#    print(d)
    k_l=list(d.keys())
    v_l=list(d.values())
#    print(k_l)

    x=0
    sk=k_l[x]
    dq=deque()
    dq.append(sk)
#    while dq:
#    print(dq)
#    x=0
    seen=[]
    while dq:
#    while n<10:
        k=dq.pop()
        k_ll=d[k]
        seen.append(k)
#        print(k_ll)
        for i in k_ll:
            if i not in seen:
                dq.append(i)
#        d=d.pop(sk)
#        print(dq)
        x+=1
#    print(set(seen),len(set(seen)))
    if len(set(seen))!=n:
        cnt+=1
print(cnt)

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    a = [list(map(int,input().split())) for _ in range(M)]
    count = 0
    def bridge(X):
        go = [False for _ in range(N)]
        queue = [0]
        while queue:
            a = queue.pop()
            for i in X[a]:
                if not go[i]:
                    go[i] = True
                    queue.append(i)
        if all(go):
            return 1
        else:
            return 0
    for i in range(M):
        b = a[:i]+a[i+1:]
        road = [[] for _ in range(N)]
        for j in range(M-1):
            road[b[j][0]-1].append(b[j][1]-1)
            road[b[j][1]-1].append(b[j][0]-1)
        count += bridge(road)

    print(M-count)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0

for i in ab:
    vertex = list(range(N))
    for j in ab:
        if i != j:
            vertex = [vertex[j[0] - 1] if vertex[k] == vertex[j[1] - 1] else vertex[k] for k in range(N)]
    if len(set(vertex)) != 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# pdf解法（隣接行列でグラフを管理して、DFSで連結判定する）
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        # xに繋がっている頂点をたどっていく
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False]*N for _ in range(N)]   # 隣接行列
visited = [False]*N

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

ans = 0
for i, e in enumerate(edge):
    # 辺を取り除く
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    # 初期化（全ての頂点を未訪問にする）
    for j in range(N):
        visited[j] = False

    # 任意の１つの頂点からDFS
    dfs(0)

    # 連結判定（訪問していない頂点がある＝非連結）
    bridge = False
    for j in range(N):
        #if not visited[j]:
        if not all(visited):
            bridge = True
    if bridge:
        ans += 1

    # 取り除いた辺を戻す
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)

Submission status: Accepted

Solution code:
# pdf解法（隣接行列でグラフを管理して、DFSで連結判定する）
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        # xに繋がっている頂点をたどっていく
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False]*N for _ in range(N)]   # 隣接行列
visited = [False]*N

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

ans = 0
for i, e in enumerate(edge):
    # 辺を取り除く
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    # 初期化（全ての頂点を未訪問にする）
    for j in range(N):
        visited[j] = False

    # 任意の１つの頂点からDFS
    dfs(0)

    # 連結判定（訪問していない頂点がある＝非連結）
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    if bridge:
        ans += 1

    # 取り除いた辺を戻す
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)

Submission status: Accepted

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

answer=0

for some  in range(m):
    ans=0
    for i in range(1,n+1):
        cnt=0
        for _ in lists:
            if _[0]==i or _[1]==i:
                cnt+=1
                index=lists.index(_) 
        if cnt==1:
            ans+=1
            del lists[index]
        else:
            ans+=0
            continue
    answer+=ans
print(answer)

Submission status: Accepted

Solution code:
# pdf解法（隣接行列でグラフを管理して、DFSで連結判定する）
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(N):
        # xに繋がっている頂点をたどっていく
        if graph[x][i]:
            dfs(i)


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

edge = []
graph = [[False for _ in range(N)] for _ in range(N)]   # 隣接行列
visited = [False for _ in range(N)]

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

ans = 0
for i, e in enumerate(edge):
    # 辺を取り除く
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

    # 初期化（全ての頂点を未訪問にする）
    for j in range(N):
        visited[j] = False

    # 任意の１つの頂点からDFS
    dfs(0)

    # 連結判定（訪問していない頂点がある＝非連結）
    bridge = False
    for j in range(N):
        if not visited[j]:
            bridge = True
    if bridge:
        ans += 1

    # 取り除いた辺を戻す
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

print(ans)

Submission status: Accepted

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

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

cnt = 0

from collections import deque

for i in a:
    b = a[:]
    start = i[0]
    goal = i[1]
    b.remove(i)
    q = deque()
    q.append(start)

    searched = {start}
    while q:
        current = q.popleft()
        if current == goal:
            break
        for j in b:
            if current == j[0] and j[1] not in searched:
                q.append(j[1])
                searched.add(j[1])
            elif current == j[1] and j[0] not in searched:
                q.append(j[0])
                searched.add(j[0])
    else:
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
def BFS(n, graph): #隣接リストのグラフが連結かどうかを判定する。連結でなければ1を返す。
  q = deque()
  q.append(0)
  searched = {0}
  while q:
    current = q.popleft()
    for v in graph[current]: #currentと隣接じている点のリスト
      if v not in searched:
        searched.add(v)
        q.append(v)
  
  if len(searched) != n:
    return 1
  else:
    return 0
  
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
edges = []
ans = 0

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

import copy
for edge in edges:
  g = copy.deepcopy(graph) #普通のcopyだとうまくいかない
  #辺edgeの削除を行う
  g[edge[0]].remove(edge[1])
  g[edge[1]].remove(edge[0])
  ans += BFS(n, g) #辺の削除により非連結になるならばその辺は橋

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edgelist = []
edgelistappend = edgelist.append
for i in range(M):
    edgelistappend(set(map(int, input().split())))
bridge = set()
S = set()

for e in edgelist:
    if tuple(e) not in S:
        flag = True
        E = list(e)
        start = E[0]
        goal = E[1]
        n = [start]
        R = [e]
        L = [[i for i in edgelist if (n[-1] in i) and (i not in bridge) and (i != e)]]
        while n != []:
            if n[-1] == goal:
                for x in R:
                    S.add(tuple(x))
                R.pop()
                L.pop()
                n.pop()
                flag = False
            elif L[-1] == []:
                R.pop()
                L.pop()
                n.pop()
            else:
                p = L[-1].pop()
                R.append(p)
                lp = list(p)
                if lp[0]==n[-1]:
                    n.append(lp[1])
                else:
                    n.append(lp[0])
                L.append([i for i in edgelist if (n[-1] in i) and (i not in bridge) and ((list(i)[0] not in n) or (list(i)[1] not in n))])
        if flag:
            bridge.add(tuple(e))
print(len(bridge))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n


    def root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.root(self.table[x])
            return self.table[x]


    def is_same(self, x, y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False


    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2




n, m = LI()
L = LIR(m)
cnt = 0
for i in range(m):
    U = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        a, b = L[j]
        U.union(a - 1, b - 1)
    if all([U.is_same(0, k) for k in range(n)]):
        continue
    else:
        cnt += 1



print(cnt)

Submission status: Accepted

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

C=[[0 for _ in range(N)] for _ in range(N)]
for ab in AB:
  C[ab[0]-1][ab[1]-1]=1
  C[ab[1]-1][ab[0]-1]=1
#print(C)

ans=0
D=[0]*N

def dfs(n):
  if D[n]==0:
    D[n]=1
    for i in range(N):
      if C[n][i]==1:
        dfs(i)
      
for i,ab in enumerate(AB):
  C[ab[0]-1][ab[1]-1]=0
  C[ab[1]-1][ab[0]-1]=0

  if i<M-1:
    dfs(AB[i+1][0]-1)
  else:
    dfs(AB[i-1][0]-1)
  if sum(D)!=N:
    ans+=1  

  D=[0]*N
  C[ab[0]-1][ab[1]-1]=1
  C[ab[1]-1][ab[0]-1]=1
  
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dic = {}
ab = []
for i in range(m):
  a, b = map(int, input().split())
  if a in dic.keys():
    dic[a] += [b]
  else:
    dic[a] = [b]
  if b in dic.keys():
    dic[b] += [a]
  else:
    dic[b] = [a]
  ab.append([a, b])
  
ans = 0
for pair in ab:
  a = pair[0]
  b = pair[1]
  dic[a] = [num for num in dic[a] if num != b]
  dic[b] = [num for num in dic[b] if num != a]

  serch_spot = [a]
  visited = []
  while len(serch_spot) != 0:
    spot = serch_spot.pop(0)
    visited.append(spot)
    Next_cands = dic[spot]
    for cand in Next_cands:
      if cand in visited:
        continue
      elif cand in serch_spot:
        continue
      else:
        serch_spot.append(cand)
  if len(visited) != n:
    ans += 1
  dic[a] += [b] 
  dic[b] += [a]

print(ans)

Submission status: Accepted

Solution code:
a, b = map(int,input().split())
l = [[0]*50 for i in range(50)]
m = [0]*50
L = []
def cal(v):
    m[v] = 1
    for i in range(a):
        if l[v][i] == 0:continue
        if m[i]==1 : continue
        cal(i)
for i in range(b):
    ta , tb = map(int,input().split())
    ta-=1
    tb-=1
    L.append([ta,tb])
    l[ta][tb]+=1
    l[tb][ta]+=1
c = 0

for x,y in L:
    l[x][y] = 0
    l[y][x] = 0
    m = [0]*50

    cal(0)

    flag = 0
    for i in range(a): 
        if m[i] == 0:flag=1
    c+=flag
    # print(x,y,flag)
    l[x][y] = 1
    l[y][x] = 1
print(c)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n + 1))
        self.ranks = [0 for _ in range(n + 1)]

    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


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

count = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if j == i:
            continue
        uf.merge(*ls[j])
    for i in range(n + 1):
        uf.get_root(i)
    if len(set(uf.parents[1:])) > 1:
        count += 1
print(count)

Submission status: Accepted

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

answer = 0
for x in edges:
    l = 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: answer += 1
print(answer)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

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

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x])
            self.parent[x] = rx
            return rx

    def size(self, x):
        return -self.parent[self.root(x)]
    
    def same(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        return ra == rb
    
    def merge(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return False
        if self.parent[a] > self.parent[b]:
            a, b = b, a
        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True

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

ans = 0
for i in range(0, M):
    uf = UnionFind(N)
    for j in range(0, M):
        if i == j:
            continue
        uf.merge(edges[j][0], edges[j][1])
    same = True
    ans = ans + (uf.same(edges[i][0], edges[i][1]) == False)


print(ans)

Submission status: Accepted

Solution code:
# ABC075C - Bridge
# find the number of bridges in a given undirected connected graph
# bridge := an edge whose removal disconnects a graph
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int) -> None:
    seen[v] = 1  # make vertex v searched
    for u in g[v]:
        if not seen[u]:
            dfs(u)


def main():  # O(M(N + M))
    global g, seen
    N, M, *E = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(E)] * 2):
        G[v].append(u), G[u].append(v)
    bridges = 0
    for v, u in zip(*[iter(E)] * 2):
        g = [v.copy() for v in G]  # subgraph of G except E(v, u)
        g[v].remove(u), g[u].remove(v)
        seen = [0] * (N + 1)
        dfs(1)  # search from vertex 1
        bridges += 1 if 0 in seen[1:] else 0
    print(bridges)


if __name__ == "__main__":
    main()