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())
e = [0]*(n)
for i in range(n):
    e[i] = []
c = []
for i in range(m):
    a,b = map(int,input().split())
    c.append([a-1,b-1])
    e[a-1].append(b-1)
    e[b-1].append(a-1)

def dfs(g,s,e):
    vis = []
    q = []
    vis.append(s)
    for i in range(len(g[s])):
        q.append(g[s][i])
    while len(q):
        ne = q.pop()
        vis.append(ne)
        if ne == e:
            return 1
        for i in range(len(g[ne])):
            if g[ne][i] in vis:
                continue
            if g[ne][i] == e:
                return 1
            q.append(g[ne][i])
            vis
    return 0
ans = 0
for i in range(len(c)):
    vis =[]
    f = 0
    fr = c[i][0]
    end = c[i][1]
    e[fr].remove(end)
    e[end].remove(fr)
    if dfs(e,fr,end) is 0:
        ans += 1
    e[fr].append(end)
    e[end].append(fr)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.data = []
        for i in range(N):
            self.data.append(-1)
    def root(self, a):
        if self.data[a] < 0:
            return a
        else:
            self.data[a] = self.root(self.data[a])
            return self.data[a]
    def same(self, a, b):
        if self.root(a) == self.root(b):
            return 1
        else:
            return 0
    def unite(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return 0
        if self.data[a] < self.data[b]:
            self.data[a] += self.data[b]
            self.data[b] = a
        else:
            self.data[b] += self.data[a]
            self.data[a] = b
        return 1
s = input().split(" ")
N = int(s[0])
M = int(s[1])
a = []
b = []
for i in range(M):
    s = input().split(" ")
    a.append(int(s[0]) - 1)
    b.append(int(s[1]) - 1)
res = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j != i:
            uf.unite(a[j], b[j])
    if uf.same(a[i], b[i]) == 0:
        res += 1
print(res)

Submission status: Accepted

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

nb = [[0 for x in range(n)] for y in range(n)]
inp = [list(map(int, input().split())) for x in range(m)]
for start, end in inp:
    nb[start - 1][end - 1] = 1
    nb[end - 1][start - 1] = 1


# start, end = 1, 2
# nb[start - 1][end - 1] = 0
# nb[end - 1][start - 1] = 0
#
# for i in nb: print(*i)

def can(f):
    end = [0 for x in range(n)]
    que = [(0, f[0])]

    while que:
        index, targets = que.pop()
        for ti, target in enumerate(targets):
            if target and not end[ti]:
                que.append((ti, f[ti]))
        end[index] = 1
    return end.count(1) == n
#
# can(nb)

count = 0
for start, end in inp:
    nb[start - 1][end - 1] = 0
    nb[end - 1][start - 1] = 0

    if not can(nb):
        # print(start, end)
        count += 1

    nb[start - 1][end - 1] = 1
    nb[end - 1][start - 1] = 1
print(count)

# count = 0
# for index, i in enumerate(nb):
#     if i.count(1) == 1:
#         count += 1
#         nb[index] = [0 for x in range(n)]
#         for row in nb:
#             row[index] = 0
#
# print()
# for i in nb: print(*i)
#
# print(count)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import copy

def is_connect(adj):
    is_already = defaultdict(bool)
    is_already[list(adj.keys())[0]] = True;

    queue = []
    queue.append(1)
    while len(queue) > 0:
        v = queue.pop()
        for node in adj[v]:
            if not is_already[node]:
                is_already[node] = True
                queue.append(node)

    return all([is_already[node] for node in adj.keys()])

def solve(n,m,adj,edges):
    ans = 0
    for (v1, v2) in edges:
        tmp_adj = copy.deepcopy(adj)
        tmp_adj[v1].remove(v2)
        tmp_adj[v2].remove(v1)
        if not is_connect(tmp_adj):
            ans += 1

    return ans

def main():
    s = sys.stdin.readline().rstrip()
    lst = s.split(' ')
    n = int(lst[0])
    m = int(lst[1])

    adj = defaultdict(list)
    edges = []

    for i in range(m):
        s = sys.stdin.readline().rstrip()
        lst = s.split(' ')
        a = int(lst[0])
        b = int(lst[1])
        edges.append((a,b))
        if not b in adj[a]:
            adj[a].append(b)

        if not a in adj[b]:
            adj[b].append(a)

    ans = solve(n,m,adj,edges)
    print(ans)
    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
adjacent = [[0 for _ in xrange(n)] for _ in xrange(n)]
for _ in xrange(m):
    i, j = map(int, raw_input().split())
    adjacent[i-1][j-1] = 1
    adjacent[j-1][i-1] = 1

bridge = []
count = 0
while(1):
    for i in xrange(n):
        if sum(adjacent[i]) == 1:
            for j in xrange(n):
                if adjacent[i][j] == 1:
                    if ([i,j] not in bridge) and ([j,i] not in bridge):
                        bridge.append([i,j])
                        count += 1
    if not any(bridge): break
    for i,j in bridge:
        adjacent[i][j] = 0
        adjacent[j][i] = 0
    bridge = []
print count

Submission status: Accepted

Solution code:
#深さ優先探索
def dfs(Graph, Start, pl, parent, Visited=None):
    if (Visited==None):  Visited = [] #開始点のときに探索済みリストをつくる
    Visited.append(Start)  #現在の頂点を探索済みリストに加える
    pre[Start] = pl
    low[Start] = pl
    pl += 1
    for Next in Graph[Start]:  #次に探索する頂点の候補
        if Next == parent:
            continue
        if ( Next in Visited ):
            low[Start] = min(low[Start], low[Next])
            continue  #訪問済みリストにある頂点は飛ばす
        loww = dfs(Graph, Next, pl,Start, Visited)  #再帰
        low[Start] = min(low[Start], loww)
    return low[Start]


N, M = (int(i) for i in input().split())

inp = [[int(i) for i in input().split()] for i in range(M)]

pre = [0 for _ in range(N+1)]
low = [0 for _ in range(N+1)]

# 隣接リスト
l = [[] for i in range(N+1)]
for pi in inp:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])

dfs(l, 1, 1, 0)

cnt = 0
for i in range(2,N+1):
    if pre[i]==low[i]:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

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

ans = 0
for i in range(n):
    for j in range(i):
        if g[i][j] == 1:
            g[i][j] = g[j][i] = 0

            vis = [False for _ in range(n)]
            vis[0] = True
            q = queue.Queue()
            q.put(0)
            while not q.empty():
                v = q.get()
                for e in range(n):
                    if g[v][e] == 1 and not vis[e]:
                        vis[e] = True
                        q.put(e)

            add = 0
            for k in range(n):
                if not vis[k]:
                    add = 1
            ans += add

            g[i][j] = g[j][i] = 1

print(ans)

Submission status: Accepted

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

G = dict()
G2 = dict()
for i in range(1, N+1):
    G[i] = []
    G2[i] = []
    
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)


pre_list = [0]*(N+1)
low_list = [0]*(N+1)
par_list = [0]*(N+1)

res = 0

que = [1]
pre_no = 0


while len(que) > 0:
    p = que.pop()
    if pre_list[p] == 0:
        pre_no += 1
        pre_list[p] = pre_no
        low_list[p] = pre_no
    
    for q in G[p]:
        if pre_list[q] == 0:
            par_list[q] = p
            que.append(q)
            G2[q].append(p)
        elif par_list[p] != q:
            G2[q].append(p)
            
que = list(range(1, N+1))
while len(que) > 0:
    p = que.pop()
    for q in G2[p]:
        if low_list[q] > low_list[p]:
            low_list[q] = low_list[p]
            que.append(q)
            
res = -2
for i in range(N+1):
    if pre_list[i] == low_list[i]:
        res += 1
        
print(res)

Submission status: Accepted

Solution code:
import math,heapq,collections,sys,numpy as np
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def is_connected(npmat):
    mat = np.copy(npmat)
    dim = mat.shape[0]
    for i in range(dim):
        mat[i][i] = 0
    accessible = set([0])
    queue = [0]
    while len(queue) > 0:
        i = queue.pop()
        js = filter(lambda x:x[1], enumerate(mat[i] > 0))
        for j, bool in js:
            if not j in accessible:
                accessible.add(j)
                if len(accessible) == dim :
                    return True
                queue.append(j)
    return len(accessible) == dim

N,M = LI()
ma = [[0]*N for _ in range(N)]
Ms = []

for _ in range(M):
    a,b = LI_()
    ma[a][b] = 1
    ma[b][a] = 1
    Ms.append((a,b))

ans = 0
for m in Ms:
    ma[m[0]][m[1]] = 0
    ma[m[1]][m[0]] = 0
    if not is_connected(np.array(ma)):
        ans += 1
    ma[m[0]][m[1]] = 1
    ma[m[1]][m[0]] = 1
    
print(ans)

Submission status: Accepted

Solution code:
def dfs(linesdata,visitlist,point):
 visitlist.append(point)
 for line in linesdata:
  if point == line[0] and not line[1] in visitlist:
   dfs(linesdata,visitlist,line[1])
  elif point == line[1] and not line[0] in visitlist:
   dfs(linesdata,visitlist,line[0])
import copy
data=raw_input().split(' ')
points=int(data[0])
lines=int(data[1])
lineslist=[]
count=0
for x in range(lines):
 pts=raw_input().split(' ')
 lineslist.append((int(pts[0])-1,int(pts[1])-1))
for index in range(lines):
 newlines=copy.deepcopy(lineslist)
 newlines[index]=[-1,-1]
 vislist=[]
 dfs(newlines,vislist,0)
 if not sorted(vislist)==range(points):
  count+=1
print count

Submission status: Accepted

Solution code:
def dfs(v, p, a):
    global ans
    # print(v, p, a, ans)
    # print(pre)
    # print(low)
    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]


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

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

ans = 0
pre = [-1] * n
low = [-1] * n
dfs(0, 0, None)
print(ans - 1)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))


n,m = readLine_int_list()
g = [[] for j in range(n)]

for i in range(m):
    a,b = readLine_int_list()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    

prenum = [None] * n
parent = [None] * n
lowest = [None] * n
counter = 0
bridges = set()
 
 
def dfs(cur, prev):
    global counter
    prenum[cur] = lowest[cur] = counter
    counter += 1
    for edge in g[cur]:
        if prenum[edge] is not None:
            if edge != prev:
                lowest[cur] = min(lowest[cur], prenum[edge])
            continue
        parent[edge] = cur
        dfs(edge, cur)
        lowest[cur] = min(lowest[cur], lowest[edge])
    if prenum[cur] == lowest[cur]:
        bridges.add((cur, prev) if cur < prev else (prev, cur))

def main():
    dfs(0, -1)
    print(len(bridges)-1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
inputs = input().split()
N = int(inputs[0])
M = int(inputs[1])

grid_list = [[] for x in range(N)]
input_edge = []

diff = 0
for i in range(N):
    diff += i

for M in range(M):
    inputs = input().split()
    a = int(inputs[0])
    b = int(inputs[1])
    input_edge.append([a-1, b-1])
    grid_list[a - 1].append(b-1)
    grid_list[b-1].append(a-1)



ans = 0
for inp in input_edge:
    grid_list[inp[0]].remove(inp[1])
    grid_list[inp[1]].remove(inp[0])
    able_list = []
    sum = 0
    search_list = []
    for g in grid_list[0]:
        search_list.append(g)
    for g in search_list:
        able_list.append(g)
        for h in grid_list[g]:
            if h not in search_list:
                search_list.append(h)
    able_list = list(set(able_list))
    for i in able_list:
        sum += i
    if diff > sum:
        ans += 1
    grid_list[inp[0]].append(inp[1])
    grid_list[inp[1]].append(inp[0])

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
n,m=[int(x) for x in input().split()]
d=[set() for x in [0]*n]
pair=[]
for i in [0]*m:
    a,b=[int(x)-1 for x in input().split()]
    d[a].add(b)
    d[b].add(a)
    pair.append((a,b))
ans=0
from collections import deque
def road(a,b):
    d[a].remove(b)
    d[b].remove(a)
    que=deque()
    que.append(a)
    aset={a}
    while que:
        t=que.popleft()
        if t==b:
            d[a].add(b)
            d[b].add(a)
            return False
        for e in d[t]:
            if e in aset:
                continue
            aset.add(e)
            que.append(e)
    d[a].add(b)
    d[b].add(a)
    return True
for a,b in pair:
    if road(a,b):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = list(map(int, input().split()))
A = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(M):
    a, b = list(map(int, input().split()))
    A[a][b] = 1
    A[b][a] = 1

br = 0
t = True
while(t):
    t = False
    for i in range(N+1):
        c = 0
        k = -1
        for j in range(len(A[i])):
            if (A[i][j] == 1):
                c += 1
                k = j
        if (c == 1):
            t = True
            A[i][k] = 0
            A[k][i] = 0
            br += 1
print(br)

Submission status: Accepted

Solution code:
import copy
N,M = input().split()
N,M = int(N),int(M)
graph = []

node = [[] for N in range(N+1)]

for m in range(M):
    tmp0 = list(map(int,input().split()))
    tmp1 = copy.deepcopy(tmp0)
    tmp1.reverse()
    node[tmp0[0]].append(tmp0)
    node[tmp1[0]].append(tmp1)

counter = 0
flag = True

while flag:
    for n in range(len(node)):
        if len(node[n]) == 1:
            tmp = copy.deepcopy(node[n][0])
            tmp.reverse()
            node[n].pop()
            counter += 1
            for k in range(len(node[tmp[0]])):
                if node[tmp[0]][k] == tmp:
                    node[tmp[0]].remove(tmp)
                    break

    flag = False
    for _ in node:
        if len(_) == 1:
            flag = True
            break
        
print(counter)

Submission status: Accepted

Solution code:
import copy

from collections import deque


def check(s):
    que = deque()
    que.append(s)
    while len(que) != 0:
        tmp_ele = que.pop()
        flgs[tmp_ele] = True
        for ele in tmp_G[tmp_ele]:
            if not flgs[ele]:
                que.append(ele)

    for flag in flgs:
        if not flag:
            return False
    else:
        return True


if __name__ == '__main__':
    N, M = map(int, input().split())
    graph_list = []

    for i in range(M):
        tmp_a, tmp_b = map(int, input().split())
        graph_list.append((tmp_a, tmp_b))

    G = [[] for _ in range(N + 1)]
    for a, b in graph_list:
        G[a].append(b)
        G[b].append(a)

    ans = 0

    for a, b in graph_list:
        tmp_G = copy.deepcopy(G)
        tmp_G[a].remove(b)
        tmp_G[b].remove(a)
        flgs = [False for _ in range(N + 1)]
        flgs[0] = True
        if not check(1):
            ans += 1

    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc075/tasks/abc075_c

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline



def solve(es, degrees, N, M):
    bridge = 0
    Q = []

    for i in range(1, N+1):
        if degrees[i] == 1:
            Q.append(i)

    while Q:
        u = Q.pop()
        bridge += 1
        for e in es[u]:
            degrees[e] -= 1
            if degrees[e] == 1:
                Q.append(e)

    return bridge



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

    degrees = [0] * (N + 1)
    es = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        es[a].append(b)
        es[b].append(a)
        degrees[a] += 1
        degrees[b] += 1

    result = solve(es, degrees, N, M)
    print(min(result, M))



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

# UnionFindDataStructure
def find(v):
    if parent[v] == v:
        return v
    else:
        parent[v] = find(parent[v])
        return parent[v]

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    parent[rootB] = rootA


ans = 0
for edge in edges:

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

    for (a, b) in edges:
        if (a, b) == edge: continue
        union(a, b)

    for v in range(N):
        find(v)

    if len(set(parent)) > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)


N,M = map(int,raw_input().split(" "))
path = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,raw_input().split(" "))
    a-=1
    b-=1
    path[a].append((b,i))
    path[b].append((a,i))




vmemo = [0 for i in range(N)]
ememo = [1 for i in range(M)]

stk = []

def loop(pos,last_edge):
    global stk,vmemo,ememo
    
    if vmemo[pos]:
        for i in range(len(stk)-1,-1,-1):
            _v,_e = stk[i]
            ememo[_e] = 0
            if _v == pos:
                return pos
    
    vmemo[pos] = 1
    for v,e in path[pos]:
        if e != last_edge:
            stk.append((pos,e))
            _p = loop(v,e)
            stk.pop()
    vmemo[pos] = 0

    return -1



loop(0,-1)

print(ememo.count(1))

Submission status: Accepted

Solution code:
import queue

N, M = map(int, input().split())
path = [0]*(N+1)

for i in range(N+1):
    path[i] = []

paths = []

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


ans = 0
for none in paths:
    dp = [False]*(N+1)
    dp[0] = True
    
    q = queue.Queue()
    q.put(1)
    while not q.empty():
        now = q.get()
        for e in path[now]:
            if not none in [(now, e), (e, now)]:
                if not dp[e]:
                    dp[e] = True
                    q.put(e)

    if False in dp:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
def bridge(g, v, s=0):
    bl = [False] * v
    c_memo = [0] * v
    c_used = [False] * v
    b_g = [[] for i in range(v)]
    def dfs(v, f, l):
        bcnt = fcnt = 0
        c_used[v] = True
        for t in g[v]:
            if not c_used[t]:
                ll = []
                ret = dfs(t, v, ll)
                if ret>0:
                    l += ll
                else:
                    b_g[t] = ll
                    for u in ll:
                        b_g[u].append(t)
                    l.append(t)
                bcnt += ret
            else:
                if t==f:
                    if fcnt==1:
                        c_memo[f] -= 1
                        bcnt += 1
                    fcnt += 1
                elif not bl[t]:
                    c_memo[t] -= 1
                    bcnt += 1
        bl[v] = True
        bcnt += c_memo[v]
        return bcnt
    dfs(s, -1, b_g[s])
    for u in b_g[s]:
        b_g[u].append(s)
    return b_g
G = bridge(G, n)
ans = 0
for i in range(n):
    for v in G[i]:
        if i < v:
            ans += 1
print(ans)

Submission status: Accepted

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

sets = []
for _ in range(m):
    (a, b) = map(lambda x:int(x)-1, input().split(" "))
    sets += [(a, b)]

num = 0
for (a, b) in sets:
    gi = [[False for _ in range(n)] for _ in range(n)]
    for (x, y) in sets:
        gi[x][y] = True
        gi[y][x] = True
    
    gi[a][b] = False
    gi[b][a] = False
     
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if gi[i][k] and gi[k][j]:
                    gi[i][j] = True
    
    found = False
    for i in range(n):
        for j in range(n):
            if not gi[i][j]:
                found = True
                break
        if found:
            num += 1
            break

print(num)

Submission status: Accepted

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

edge = []
for i in xrange(M):
  edge.append(map(lambda x: int(x)-1, raw_input().split(' ')))

ans = 0
for ex in xrange(M):
  n = []
  for i in xrange(N):
    n.append({})
  for i in xrange(M):
    if i == ex: continue
    a, b = edge[i]
    n[a][b] = n[b][a] = 1

  cl = set()
  op = set([0])
  while len(op) > 0:
    a = op.pop()
    cl.add(a)
    for to in n[a]:
      if to not in cl:
        op.add(to)

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

print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

import itertools


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes

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

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def count_bridges(n, m, edges):
    res = 0
    for rem_idx in range(m):
        uf = UnionFind(n)
        for i in range(m):
            if i != rem_idx:
                a, b = edges[i]
                uf.unite(a, b)
        for u, v in itertools.product(range(n), repeat=2):
            if not uf.in_the_same_set(u, v):
                res += 1
                break
    return res


def main():
    n, m = (int(x) for x in input().split())
    edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]
    print(count_bridges(n, m, edges))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

cnt = 0
for i in range(N):
	for j in edge[i]:
		E = [[n for n in edge[m] if not((n,m)==(i,j) or (n,m)==(j,i))] for m in range(N)]
		searched = []
		search = [i]

		while len(search) > 0:
			s = search.pop(0)
			if s in searched:
				continue
			searched.append(s)
			for v in E[s]:
				search.append(v)
		if len(searched) < N:
			cnt += 1
print(int(cnt/2))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
rank=[100000 for i in range(n)]
low=[100000 for i in range(n)]
visited=[False for i in range(n)]
k=0
def dfs(pos,parent):
    global k
    rank[pos]=low[pos]=k
    k+=1
    visited[pos]=True
    for i in edge[pos]:
        if not visited[i]:
            dfs(i,pos)
            low[pos]=min(low[pos],low[i])
        elif i!=parent:
            low[pos]=min(low[pos],rank[i])
dfs(0,-1)
cnt=0
for i in range(n):
    for j in edge[i]:
        if low[i]>rank[j]:
            cnt+=1
print(cnt)

Submission status: Accepted

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

parent = None
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;

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

Submission status: Accepted

Solution code:
def dfs(i):
    global nodes, flags
    if flags[i]:
        return
    flags[i]=True
    for n in nodes[i]:
        dfs(n)
    
    
    


line=input().split()
n=int(line[0])
m=int(line[1])

edges=[] #[a,b] for every edge
nodes=[[] for i in range (n)] #list of all neighbours for all nodes
flags=[False for i in range(n)]
for i in range(m):
    line=input().split()
    a=int(line[0])-1
    b=int(line[1])-1
    edges.append([a,b])
    nodes[a].append(b)
    nodes[b].append(a)
count=0
for i in range(m):
    a=edges[i][0]
    b=edges[i][1]
    nodes[a].remove(b)
    nodes[b].remove(a)
    dfs(0)
    bridge=False
    for j in range(n):
        if flags[j]==False:
            bridge = True
        flags[j]=False
    if bridge:
        count+=1
    nodes[a].append(b)
    nodes[b].append(a)
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for i in range(n)]
E = []
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    E.append((a-1, b-1))
from collections import deque
def solve(s, t):
    if len(G[s]) == 1 or len(G[t]) == 1:
        return 1
    used = [0]*n
    que = deque()
    used[s] = 1
    for v in G[s]:
        if v == t:
            continue
        used[v] = 1
        que.append(v)
    while que:
        u = que.popleft()
        for v in G[u]:
            if not used[v]:
                used[v] = 1
                que.append(v)
    return sum(used) != n
ans = 0
for a, b in E:
    ans += solve(a, b)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,m = LI()
    e = collections.defaultdict(set)
    k = []
    for _ in range(m):
        a,b = LI_()
        e[a].add(b)
        e[b].add(a)
        k.append((a,b))

    # メソッドのみ版
    def search(s):
        d = [inf] * n
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv in e[u]:
                ud = 1
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    r = 0
    for a,b in k:
        e[a].remove(b)
        e[b].remove(a)
        d = search(0)
        if max(d) == inf:
            r += 1
        e[a].add(b)
        e[b].add(a)

    return r


print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def dfs(i, used, g, ng):
    for n in g[i]:
        if n not in used and (i, n) != ng and (n, i) != ng:
            used.add(n)
            dfs(n, used, g, ng)


def main():
    N, M = map(int, input().split())
    g = defaultdict(list)
    k = []
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
        k.append((a, b))

    ans = 0
    for a, b in k:
        used = set()
        dfs(1, used, g, (a, b))
        if len(used) != N:
            ans += 1
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()


upper = [0]

def root(x):
    if upper[x] < 0:
        return x
    else:
        upper[x] = root(upper[x])
        return upper[x]

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

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        if upper[y] < upper[x]:
            x, y = y, x
        upper[x] += upper[y]
        upper[y] = x
    return x == y

n, m = na()
es = []
for i in range(m):
    es.append(na())

ret = m
for i in range(m):
    upper = [-1] * n
    for j in range(m):
        if j != i:
            unite(es[j][0]-1, es[j][1]-1)
    for j in range(n):
        if upper[j] == -n:
            ret -= 1

print(ret)

Submission status: Runtime Error

Solution code:
import queue
n, m = map(int, input().split())
route = [[] for _ in range(n)]
vals = []
for _ in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
    route[b-1].append(a-1)
    vals.append([a-1, b-1])
ans = m
for i in range(m):
    route2 = set()
    q = queue.Queue()
    q.put(i)
    try:
        route[vals[i][0]].remove(vals[i][1])
        route[vals[i][1]].remove(vals[i][0])
    except:
        pass
    while not q.empty():
        a = q.get()
        if not a in route2:
            route2.add(a)
            for j in route[a]:
                q.put(j)
        if len(route2) == n:
            ans -= 1
            break
    try:
        route[vals[i][0]].append(vals[i][1])
        route[vals[i][1]].append(vals[i][0])
    except:
        pass
print(ans)