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

#print(list(uf.all_group_members().values())) #グループ一覧を表示
#0-indexed n=5なら頂点の名前は0,1,2,3,4

n,m=map(int,input().split())
uf=UnionFind(n)
ans=0
a=[[int(i) for i in input().split()]for i in range(m)]

for i in a:
    x,y=i
    uf.union(x-1,y-1)
cnt=uf.group_count()

for i in range(m):
    uf_new=UnionFind(n)
    for j in range(m):
        x,y=a[j]
        if j==i:
            continue
        uf_new.union(x-1,y-1)
    cnt_new=uf_new.group_count()
    if cnt!=cnt_new:
        ans+=1
print(ans)

Submission status: Accepted

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



def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

def size(x):
    return -par[find(x)]

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

# 一つの辺以外を繋いでその辺の両端の点が同じ集合に属していたらその辺は橋ではない
ans = 0
for i in range(M):
    par = [-1] * (N + 1)
    for j in range(M):
        if i != j:
            unite(a[j],b[j])
    if not same(a[i],b[i]):
        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)]

ans = 0

for i in range(m):
    ab2 = ab[:i] + ab[i+1:]
    uf = UnionFind(n)
    for a,b in ab2:
        uf.union(a-1,b-1)
    if uf.group_count() > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
henl = []
usehen = [False] * m
brdic = {}
for _ in range(m):
    a,b= map(int,input().split())
    brdic[a] = brdic.get(a,[]) + [b]
    brdic[b] = brdic.get(b,[]) + [a]
    henl.append((a,b))

ordin = [-1]*(n+1)
lowlink = [-1]*(n+1)
k=[1]
bn=[0]
def dfs(node):
    ordin[node]=k[0]
    k[0]+=1
    lowlink[node]=ordin[node]
    for br in brdic[node]:
        temp = (min(node,br),max(node,br))
        if ordin[br]==-1:
            usehen[henl.index(temp)]=True
            dfs(br)
            lowlink[node] = min(lowlink[br],lowlink[node])
        else:
            if usehen[henl.index(temp)]==False:lowlink[node] = min(ordin[br],lowlink[node])
        if ordin[node] < lowlink[br]:bn[0]+=1
dfs(1)
print(bn[0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(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
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split())
    AB = tuple(tuple(map(int, input().split())) for _ in range(M))

    ans = 0
    for i in range(M):
        uf = UF_tree(N)
        for j, (a, b) in enumerate(AB):
            if i == j:
                continue
            uf.unite(a, b)
        a, b = AB[i]
        if not uf.isSame(a, b):
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

def union(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x,y = y, x

    parents[x] += parents[y]
    parents[y] = x 

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

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

ans = 0
for i in range(M):
    parents = [-1] * N
    for j in range(M):
        if i == j:
            continue
        s, e = edges[j]
        union(s, e)
    a, b = edges[i]
    if not same(a, b):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#75c
import copy  
  
N,M = map(int, input().split())#M<=50

lines = set()
for _ in range(M):
    a,b = map(int, input().split())
    lines.add((a,b))

#union findを使う###############################################   
def connection_check(lines,start,goal):
    
    #接続追加
    def add_connect(A,B):
        A_parent = get_parent(A)
        B_parent = get_parent(B)

        if A_parent != B_parent:
            parent_dict[B_parent] = A_parent
    #接続有無判断
    def judge_connection(A,B):
        A_parent = get_parent(A) #未更新状態でも、ここで更新される
        B_parent = get_parent(B)

        if A_parent != B_parent:
            return False
        else:
            return True
    #親の取得
    def get_parent(child):
        if child not in parent_dict: #初出なら自分自身を親として追加
            parent_dict[child] = child
        parent = parent_dict[child]
        if parent == child:
            return parent
        else: 
            #最上位の親なら上の等式が成り立つ。不成立ならさらに上位の親を辿る。
            parent_dict[child] = get_parent(parent)
            return parent_dict[child]
    

    parent_dict = dict()
    
    for line in lines:
        A = line[0]
        B = line[1]
        add_connect(A,B)
    
    if judge_connection(start,goal) == True:
        return True
    else:
        return False
        
#################################################################
ans = 0

for line in lines:
    start = line[0]
    goal = line[1]
    remain_lines = copy.copy(lines) 
    remain_lines.remove(line)
    
    #print(start,goal)
    #print(remain_lines)
    
    if connection_check(remain_lines,start,goal) is False:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
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]
N,M = inputlist()
ans = 0
ab = [0]*M
for i in range(M):
    ab[i] = inputlist()
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j == i:
            continue
        uf.union(ab[j][0]-1,ab[j][1]-1)
    if len(uf.roots()) != 1:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
"""
DFS
"""
from collections import defaultdict
N,M = map(int, input().split())
pairs = []
for i in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    pairs.append((a,b))


def dfs(s):
    if visited[s]:return 0
    visited[s] = True
    ns = edges[s]
    for n in ns:
        dfs(n)
    
    
ans = 0  
for i in range(M):
    edges = defaultdict(list)
    visited = [False] * N
    for j,(a,b) in enumerate(pairs):
        if i == j: continue
        edges[b].append(a)
        edges[a].append(b)
    dfs(0)
    if sum(visited) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
"""
DFS
"""
from collections import defaultdict
N,M = map(int, input().split())
pairs = []
for i in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    pairs.append((a,b))


def dfs(s):
    global visited,edges
    if visited[s]:return 0
    visited[s] = True
    ns = edges[s]
    for n in ns:
        dfs(n)
    
    
ans = 0  
for i in range(M):
    edges = defaultdict(list)
    visited = [False] * N
    for j,(a,b) in enumerate(pairs):
        if i == j: continue
        edges[b].append(a)
        edges[a].append(b)
    dfs(0)
    if sum(visited) != N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
edges = defaultdict(list)
N,M = map(int, input().split())
pairs = []
for i in range(M):
    a,b  = map(int, input().split())
    a -= 1
    b -= 1
    pairs.append((a,b))
ans = 0
# M本目の辺を切って全探索
for i in range(M):
    edges = defaultdict(list)
    s = 0
    for j,(a,b) in enumerate(pairs):
        if i == j:continue
        edges[a].append(b)
        edges[b].append(a)
        s = b
    cnt = 0
    # print(i,edges)
    # bfs
    seen = [False] * N 
    q = deque()
    q.append(b) 
    while len(q) > 0:
        e = q.popleft()
        nx = edges[e]
        for n in nx:
            if seen[n]:continue
            seen[n] = True
            q.append(n)
    if sum(seen) != N:
        ans += 1


    
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木かどうかを判定する
    def ifTree(self, array):
        root = self.root(array[0])
        for v in array:
            if not self.root(v) == root:
                return False
        return True

    # 木の結合を行う。親の配下に入る
    # 木の結合がされたかを戻り値に返す

    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1
            return True
        else:
            return False

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

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


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

not_bridge_count = 0

array = [i for i in range(n)]
for i in range(m):
    tree = UnionFind(n)
    for j in range(m):
        if not j == i:
            tree.unite(edges[j][0], edges[j][1])
    if tree.ifTree(array):
        not_bridge_count += 1

print(m-not_bridge_count)

Submission status: Accepted

Solution code:
class Unionfind:
    
    def __init__(self,n):
        self.uf = [-1]*n

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

    def same(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 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

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

for i in range(m):
    
    u = Unionfind(n)
    for j in range(m):
        if i == j:
            continue
        u.union(l[j][0]-1,l[j][1]-1)
    count = set()
    for j in range(n):
        count.add(u.find(j))
    
    if len(count) > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    G = [[] for _ in range(N)]
    for i, (ai, bi) in enumerate(zip(a, b)):
        ai -= 1
        bi -= 1
        G[ai].append((i, bi))
        G[bi].append((i, ai))

    ans = 0
    for k in range(M):
        q = deque()
        visited = {0}
        q.append(0)
        while q:
            s = q.popleft()
            for i, t in G[s]:
                if i == k:
                    continue
                if t in visited:
                    continue
                visited.add(t)
                q.append(t)

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

    print(ans)


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:
f=lambda:map(int,input().split())
n,m=f()
lt=[]
ll=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  a-=1;b-=1
  lt+=[(a,b)]
  ll[a].append(b)
  ll[b].append(a)
def dfs(x):
  if lv[x]>0: return
  lv[x]=1
  for i in range(n):
    if x in ll[i]: dfs(i)
c=0
for a,b in lt:
  ll[a].remove(b)
  ll[b].remove(a)
  lv=[0]*n
  dfs(0)
  if sum(lv)<n: c+=1
  ll[a].append(b)
  ll[b].append(a)
print(c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
lt=[]
ll=[[0]*n for _ in range(n)]
for _ in range(m):
  a,b=f()
  a-=1;b-=1
  lt+=[(a,b)]
  ll[a][b]=ll[b][a]=1
def dfs(x):
  if lv[x]>0: return
  lv[x]=1
  for i in range(n):
    if ll[i][x]>0: dfs(i)
c=0
for a,b in lt:
  ll[a][b]=ll[b][a]=0
  lv=[0]*n
  dfs(0)
  if sum(lv)<n: c+=1
  ll[a][b]=ll[b][a]=1
print(c)

Submission status: Accepted

Solution code:
import copy

class UNION:
    def __init__(self):
        return
    def find(self, x):
        if par[x] < 0:
            return x
        else:
            par[x] = self.find(par[x])
            return par[x]

    # 同一の集合の判定
    def same(self, x, y):
        if self.self.find(x) == self.find(y):
            return True
        else:
            return False
    # 集合の併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x

# 集合の数
def uCnt(self,x):
    return -par[self.find(x)]

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
cpar = [-1 for i in range(N)]
jiko = []
for i in range(M):
    par = copy.deepcopy(cpar)
    u = UNION()
    for j in range(M):
        if j == i:continue
        a = ab[j][0] - 1
        b = ab[j][1] - 1
        u.unite(a, b)
    tmp = min(par)
    if tmp == -N:
        jiko.append(i)

par = copy.deepcopy(cpar)
u = UNION()
for i in range(M):
    if jiko.count(i) == 0:
        a = ab[i][0] - 1
        b = ab[i][1] - 1
        u.unite(a, b)
ans = 0
for i in par:
    if i < -1:
        ans += abs(i) - 1

print(ans)

Submission status: Accepted

Solution code:
def dfs(v):
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] and not visited[v2]:
            dfs(v2)


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

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

for e in edge:
    graph[e[0]-1][e[1]-1] = True
    graph[e[1]-1][e[0]-1] = True

ans = 0

for e in edge:
    graph[e[0]-1][e[1]-1] = False
    graph[e[1]-1][e[0]-1] = False

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

    dfs(0)

    for v in visited:
        if not v:
            ans += 1
            break

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

print(ans)

Submission status: Accepted

Solution code:
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
G = [list() for _ in range(N)]
edges = [tuple(map(int1, input().split())) for _ in range(M)]
for u,v in edges:
    G[u].append(v)
    G[v].append(u)

pre = [-1]*N
low = [-1]*N

def detect_bridge(v, p=None, c=0):
    ret = list()
    pre[v] = low[v] = c
    c += 1
    for x in G[v]:
        if x == p: continue
        if pre[x] < 0:
            br, c = detect_bridge(x, v, c)
            ret.extend(br)
             
        if low[v] > low[x]: low[v] = low[x]
    if pre[v] == low[v] > 0:
        ret.append((p, v))
    return ret, c

bridges, _ = detect_bridge(0)
print(len(bridges))

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

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ans=0
for i in range(m):
  uf=UnionFind(n)
  for j in range(m):
    if i==j:continue
    uf.unite(ab[j][0]-1,ab[j][1]-1)
  if uf.group_count()==2:
    uf.unite(ab[i][0]-1,ab[i][1]-1)
    if uf.group_count()==1:
      ans+=1
print(ans)

Submission status: Accepted

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

n, m = list(map(int, input().split()))
edges = []
graph = np.zeros((n, n), dtype=np.int)
for _ in range(m):
    edges.append(list(map(int, input().split())))
    graph[edges[-1][0]-1][edges[-1][1]-1] += 1
    graph[edges[-1][1]-1][edges[-1][0]-1] += 1

num_of_bridges = 0
for edge in edges:
    g = graph.copy()
    g[edge[0]-1][edge[1]-1] -= 1
    g[edge[1]-1][edge[0]-1] -= 1
    if connected_components(g, return_labels=False) != 1:
        num_of_bridges += 1

print(num_of_bridges)

Submission status: Accepted

Solution code:
# reference

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

adj = [list() for _ in range(n)]

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

#print(adj)
#print(list(enumerate(adj)))

loop = True
bridge = 0
while loop:
    loop = False
    for i, ai in enumerate(adj):
        if len(ai) == 1:
            adj[i] = []
            adj[ai[0]].remove(i)
            bridge += 1
            loop = True

#print(adj)
print(bridge)

Submission status: Accepted

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

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

N, M = MAP()
L = [LIST() for i in range(M)]

graph = defaultdict(list)

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


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

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

Submission status: Accepted

Solution code:
import sys
N, M = map(int, sys.stdin.readline().rstrip().split(" "))
bridges = []
for i in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split(" "))
    a, b = a - 1, b - 1
    bridges.append((a,b))

par = []
# for i in range(N):
#     par[i] = i

# siz = [1] * N

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

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

def unite(x, y):
    tmpx = root(x)
    tmpy = root(y)

    if tmpx == tmpy:
        return

    # if siz[tmpx] <= siz[tmpy]:
    #     tmpx, tmpy = tmpy, tmpx
    # siz[tmpx] += siz[tmpy]

    par[tmpy] = tmpx

ans = 0
for i in range(M):
    par = [k for k in range(N)]
    for j, e in enumerate(bridges):
        if j == i:
            continue
        a, b = e
        unite(a, b)

    a, b = bridges[i]
    if not issame(a, b):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy     
n,m = map(int,input().split())
count = 0
ab = []
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

for i in range(m):
    root = [[] for i in range(n)]
    done = [False]*n
    cd = copy.copy(ab)
    cd.pop(i)
    for j in range(m-1):
        a, b = cd[j]
        root[b-1].append(a-1)
        root[a-1].append(b-1)
        
    stack=[0]
    while len(stack):
        v = stack.pop()
        for k in root[v]:
            if done[k]: continue
            done[k] = True
            stack.append(k)
    if False in done:
        count += 1

print(count)

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
        #up_G[b-1]=a
    return G #,up_G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p,a,b):
    #(G,v,p)=(グラフ(木の情報),探索中の頂点,vの親)
    #vの子の頂点を決めて、vをpに移す
    log=[False]*n
    q=deque([])
    q.append([v,p])
    log[v-1]=True
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            #new_vが頂点の時はアウト
            if {a,b}=={V,new_v}:continue
            if new_v==P:continue
            if log[new_v-1]:continue
            log[new_v-1]=True
            q.append([new_v,V])
            break
        else:
            q.pop()

    for i in log:
        if i==False:
            return 1
    return 0

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

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

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
T = [[0]*N for i in range(N)]
G = []
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a][b] = 1
    T[b][a] = 1
    G.append((a,b))

def check(N,T):
    A = [0]*N
    Q = [0]
    while Q:
        q = Q.pop()
        if A[q]:continue
        A[q] = 1
        for c in range(N):
            if T[q][c]:
                Q.append(c)
    return sum(A)!=N

ans = 0
for g in G:
    a,b = g[0],g[1]
    T[a][b] = 0
    T[b][a] = 0
    if check(N,T):
        ans += 1
    T[a][b] = 1
    T[b][a] = 1
print(ans)

Submission status: Accepted

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


class UnionFind:
    def __init__(self, size):
        """
        size:頂点の数
        """
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        """
        xのrootを返す
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        x,yを同じグループとしてまとめる
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        """
        xとyが同じグループならTrue
        """
        return self.find(x) == self.find(y)

    def component(self):
        """
        各連結成分のrootの集合を返す
        len()をとれば連結成分の数が求められる
        return-> set()
        """
        comp = set()
        for i in self.parent:
            p = self.find(i)
            comp.add(p)
        return comp

    def __str__(self):
        """
        for debug
        クラスのlistの情報を出力
        """
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


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

for i in ab:
    uf = UnionFind(n)
    for j in ab:
        if i == j:
            continue
        uf.union(j[0] - 1, j[1] - 1)
    if not uf.same(i[0] - 1, i[1] - 1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import collections

N, M = map(int, input().split())
edge_list = [list(map(int, input().split())) for i in range(M)]
all = {i for i in range(1, N+1)}

start = 1
count = 0

for i in range(M):
    graph = collections.defaultdict(list)
    visited = {1}
    q = []
    for idx, edge in enumerate(edge_list):
        if idx != i:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
    q.extend(graph[start])
    while q:
        a = q.pop()
        if a in visited:
            continue
        else:
            visited.add(a)
            q.extend(graph[a])
    # print(all, visited)
    if all != visited:
        count += 1
print(count)