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())
s,t=[],[[] for j in range(N)]
for i in range(M):
    xx,yy=map(int,input().split())
    x,y=xx-1,yy-1
    s+=[[x,y]]
    t[x].append(y)
    t[y].append(x)
def loop(q,j,k):
    w.append(q)
    for kk in t[q]:
        if kk not in w and not (q==j and kk==k)and not(q==k and kk==j):
            loop(kk,j,k)
ans=0            
for ii in range(M):
    w=[]
    [j,k]=s[ii]
    loop(j,j,k)
    if len(w)!=N:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def c_bridge(N, M, E):
    """
    N:頂点の数
    M:辺の数
    E:辺で結ばれる頂点の組
    """
    def dfs(v):
        # 現在の頂点を訪問済にする
        visited[v] = True
        for v2 in range(N):
            # 現在の頂点と次の頂点に辺がない。スキップ
            if adjacent[v][v2] == False:
                continue
            # 次の頂点が訪問済。スキップ
            if visited[v2] == True:
                continue
            dfs(v2)

    # 隣接行列の構成
    adjacent = [[0 for _ in range(N)] for _ in range(N)]
    for a, b in E:
        a, b = a - 1, b - 1
        adjacent[a][b] = True
        adjacent[b][a] = True

    # 各辺が橋であるか？
    # グラフから辺を取り除いて、グラフが連結かを判定
    ans = 0
    for a, b in E:
        a, b = a - 1, b - 1
        # 辺を取り除く
        adjacent[a][b] = False
        adjacent[b][a] = False

        # すべての辺を未訪問として初期化
        visited = [False for _ in range(N)]
        # 頂点0からDFS
        dfs(0)
        # すべての頂点が訪問済なら連結、そうでなければ非連結
        if not all(visited):
            ans += 1

        # 辺を復元
        adjacent[a][b] = True
        adjacent[b][a] = True
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(c_bridge(N, M, E))

Submission status: Accepted

Solution code:
def dfs(g, s, u):
    s.add(u)
    if len(s) == len(g):
        return True
    for v in g[u]:
        if v not in s:
            if dfs(g, s, v):
                return True
    return False

n, m = map(int, input().split())
e = []
for _ in range(m):
    a, b = map(int, input().split())
    e.append((a - 1, b - 1))
c = 0
for i in range(m):
    g = [list() for _ in range(n)]
    for j in range(len(e)):
        if j == i: continue
        a, b = e[j]
        g[a].append(b)
        g[b].append(a)
    if not dfs(g, set(), 0): c += 1
print(c)

Submission status: Accepted

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

def connected(v,visited):
    visited[v]=1
    if sum(visited)==n:
        visited=[0]*n
        return 1
    count=0
    for i in range(n):
        if path[v][i]==1 and visited[i]==0:#行ったことある点にはいかない
            visited[i]=1#行ったことを記録
            count+=connected(i,visited)
    visited=[0]*n
    return count
bridge=0

for x in range(n):
    for y in range(x+1,n):
        if path[x][y]==1:
            visited=[0]*n
            path[x][y]=0
            if not connected(x,visited):
                bridge+=1
            path[x][y]=1
print(bridge)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
table = [[0 for j in range(n)] for i in range(n)]
v = []
for i in range(m):
    a, b = map(int,input().split())
    table[a-1][b-1] = 1
    table[b-1][a-1] = 1
    v.append((a-1,b-1))

def check(p):
    used[p] = 1
    for i in range(n):
        if p != i and table[p][i] == 1 and used[i] != 1:
            check(i)

ans = 0
for i in range(m):
    table[v[i][0]][v[i][1]] = 0
    table[v[i][1]][v[i][0]] = 0
    used = [0 for i in range(n)]
    check(0)
    if(sum(used) != n): ans += 1
    table[v[i][0]][v[i][1]] = 1
    table[v[i][1]][v[i][0]] = 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(20000000)
def check(p):
    global used
    used[p]=1
    for i in range(n):
        if(p!=i and table[p][i]==1 and used[i]!=1):
            check(i)

n,m=map(int,input().split())
v=[]
table=[[0 for i in range(n)] for i in range(n)]
for i in range(m):
    a,b=(map(int,input().split()))
    table[a-1][b-1]=1
    table[b-1][a-1]=1
    v.append((a-1,b-1))
ans=0
for i in range(m):
    table[v[i][0]][v[i][1]]=0
    table[v[i][1]][v[i][0]]=0
    used=[0 for i in range(n)]
    check(0)
    if(sum(used)!=n):
        ans+=1
    table[v[i][0]][v[i][1]]=1
    table[v[i][1]][v[i][0]]=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
graph = []
for i in range(M):
  l,r = map(int,input().split())
  graph.append((l,r))
count = 0
for j in range(M):
  queue = [graph[j][0]]
  check = [graph[j][0]]
  while len(queue) > 0:
    for k in range(M): 
      if graph[k][0] == queue[0] and graph[k][1] not in check and k != j:
        queue.append(graph[k][1])
        check.append(graph[k][1])
      elif graph[k][1] == queue[0] and graph[k][0] not in check and k != j:
        queue.append(graph[k][0])
        check.append(graph[k][0])
    queue.pop(0)
  if len(check) == N:
    count += 1
print(M - count)

Submission status: Accepted

Solution code:
def connect(blist, a):
	x = []
	for i in range(len(blist)):
		if blist[i][0]==a:
			x.append(blist[i][1])
	for j in range(len(blist)):
		if blist[j][1]==a:
			x.append(blist[j][0])
	return(x)

n,m = (int(i) for i in input().split())
y = [[int(i) for i in input().split()] for i in range(m)]
answer = m
for j in range(len(y)):
	y2,z = [],set()
	for k in range(1,n+1):
		y2.append(connect(y[:j]+y[min(j+1,len(y)):],k))
	for j2 in y2[y[j][0]-1]:
		z.add(j2)
	num = 0
	while y[j][1] not in z and len(z) != num:
		num,z2 = len(z),list(z)
		for k in z2:
			for k2 in y2[k-1]:
				z.add(k2)
	if y[j][1] in z:
		answer -= 1
print(answer)

Submission status: Accepted

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

ret = 0

for i in range(M):
    visited = [False for _ in range(N + 1)]

    queue = [1]
    visited[1] = True

    while queue:

        p = queue[0]
        queue.pop(0)

        for j, e in enumerate(edge):
            if i == j:
                continue
            if e[0] != p and e[1] != p:
                continue

            if not visited[e[0]]:
                visited[e[0]] = True
                queue.append(e[0])
            if not visited[e[1]]:
                visited[e[1]] = True
                queue.append(e[1])

    if sum(visited) != N:
        ret += 1

print(ret)

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
a = [0 for i in range(E)]
b = [0 for i in range(E)]
m = [[0 for i in range(V)] for i in range(V)]
for i in range(E):
    a[i], b[i]=map(int, input().split())
    m[a[i]-1][b[i]-1]+=1
    m[b[i]-1][a[i]-1]+=1
S=0
for n in range(E):
    m[a[n]-1][b[n]-1]-=1
    m[b[n]-1][a[n]-1]-=1
    U=[[] for i in range(V)]
    for i in range(V):
        for j in range(V):
            if m[i][j]!=0:
                U[i].append(j)
    P=[set() for i in range(E+1)]
    P[0].add(0)
    Q=set()
    R=[False for i in range(V)]
    for i in range(1,E+1):
        for u in P[i-1]:
            for v in U[u]:
                if not(R[v]):
                    R[v]=True
                    P[i].add(v)
                    Q.add(v)
        if len(P[i])==0:
            break
    if len(Q)!=V:
        S+=1
    m[a[n]-1][b[n]-1]+=1
    m[b[n]-1][a[n]-1]+=1
print(S)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
branch = dict()
a = []
b = []
for i in range(n+1):
	branch[i] = []
for i in range(m):
	atemp,btemp = map(int,input().split())
	a.append(atemp)
	b.append(btemp)
	branch[atemp].append(btemp)
	branch[btemp].append(atemp)

counter = 0
for i in range(m):
	check = True
	delindex1 = branch[a[i]].index(b[i])
	delindex2 = branch[b[i]].index(a[i])
	del branch[a[i]][delindex1]
	del branch[b[i]][delindex2]
	arrival = [0 for i in range(n+1)]
	q = [1]
	while len(q) >= 1:
		arrival[q[0]]=1
		for k in range(len(branch[q[0]])):
			if arrival[branch[q[0]][k]] == 0:
				q.append(branch[q[0]][k])
		q.pop(0)

	for k in range(1,n+1):
		if arrival[k] == 0:
			check = False
	if check==False:
		counter += 1
	branch[a[i]].append(b[i])
	branch[b[i]].append(a[i])
print(counter)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import copy

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# Set 2 dimension list
def dim2input(N):
    li = []
    for _ in range(N):
        li.append(input().split())
    return li

# --------------------------------------------

dp = None

def A_is_connected(A, edge, n_V):
    A[edge[0]][edge[1]] = False
    A[edge[1]][edge[0]] = False

    queue = [1]
    reached = [1]

    while len(queue) != 0:
        new_queue = []
        for q in queue:
            for i, is_connected in enumerate(A[q]):
                if is_connected and i not in reached:
                    new_queue.append(i)
                    reached.append(i)

        queue = new_queue

    return len(reached) == n_V


def main():
    n_V, n_E = list(map(int, input().split()))

    A = []
    for i in range(n_V+1):
        A.append([])
        for j in range(n_V+1):
            A[i].append(False)

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

    for edge in edges:
        A[edge[0]][edge[1]] = True
        A[edge[1]][edge[0]] = True

    n_bridge = 0

    for edge in edges:
        origin_A = copy.deepcopy(A)
        if not A_is_connected(A, edge, n_V):
            n_bridge += 1
        A = origin_A

    print(n_bridge)


main()

Submission status: Accepted

Solution code:
def DFS(v):
  if(already[v]==0):
    already[v]=1
    for i in range(n):
      if(con[v][i]==1):
        if(already[i]==0):
          DFS(i)


n,m=map(int,input().split())
INF=10**15
a=[-1for i in range(m)]
b=[-1for i in range(m)]
count=0
for i in range(m):
  a[i],b[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
for i in range(m):
  con=[[0 for n in range(n)]for j in range(n)]
  for j in range(n):con[j][j]=1
  already=[0 for i in range(n)]
  for j in range(m):
    if(i!=j):
      con[a[j]][b[j]]=1
      con[b[j]][a[j]]=1

  DFS(0)
  if(0 in already):count+=1
print(count)

Submission status: Accepted

Solution code:
def dfs(array, visited, next):
    if visited[next] is not True and len(array[next]) != 0:
        visited[next] = True
        for next_node in array[next]:
            visited = dfs(array, visited, next_node)
    else:
        return visited
    return visited


n, m = map(int, input().split())
edge_array = []
for i in range(m):
    edge_array.append([int(x) for x in input().split()])

cnt = 0
for _ in edge_array:
    remove_edge = edge_array[0]
    edge_array.remove(remove_edge)
    node_array = [[] for x in range(n + 1)]
    # 隣接リストの作成
    for edge in edge_array:
        node_array[edge[0]].append(edge[1])
        node_array[edge[1]].append(edge[0])
        visited = [False]*(n+1)
    res = dfs(node_array, visited, 1)
    if res.count(False) != 1:
        cnt += 1
    edge_array.append(remove_edge)

print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
pair=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
graph=[[n]*n for i in range(n)]

def dfs(v):
    if visited[v]:
        return
    visited[v]=True
    for j in [j for j,v2 in enumerate(graph[v]) if v2 == 1]:
        dfs(j)

ans = 0

for p in pair:
    graph[p[0]][p[1]] = graph[p[1]][p[0]] = 1
    
for i in range(m):
    visited=[False]*n
    x,y = pair[i]
    graph[x][y] = graph[y][x] = 0    
    dfs(0)
    
    if not all(visited):
        ans += 1
        
    graph[x][y] = graph[y][x] = 1     
    
print(ans)

Submission status: Accepted

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

pair=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
graph=[[0]*N for _ in range(N)] 


for p in pair:
	graph[p[0]][p[1]]= graph[p[1]][p[0]]=1
	
def DFS(v):
	if visited[v]:
		return 
	visited[v]=True
	for j in [j for j,v2 in enumerate(graph[v]) if v2==1]:
		DFS(j)
		
res = 0

for i in range(M):
	visited=[False for _ in range(N)] 
	x,y=pair[i]
	graph[x][y]=graph[y][x]=0 
	DFS(0)
#	DFS(0 if i>0 else 1)
	
	if not all(visited):
		res+=1
	
	graph[x][y]=graph[y][x]=1

print(res)

Submission status: Accepted

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

pair=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
graph=[[0]*N for _ in range(N)] 


for p in pair:
	graph[p[0]][p[1]]= graph[p[1]][p[0]]=1
	
def DFS(v):
	if visited[v]:
		return 
	visited[v]=True
	for j in [j for j,v2 in enumerate(graph[v]) if v2==1]:
		DFS(j)
		
res = 0

for i in range(M):
	visited=[False for _ in range(N)] 
	x,y=pair[i]
	graph[x][y]=graph[y][x]=0 
	DFS(0 if i>0 else 1)
	
	if not all(visited):
		res+=1
	
	graph[x][y]=graph[y][x]=1

print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = [[] for i in range(N)]
def dfs(bef, hr, g, vst):
	vst.add(hr)
	if hr == g:
		return 1
	cnt = 0
	for nxt in L[hr]:
		if nxt == bef or nxt in vst:
			continue
		cnt += dfs(hr, nxt, g, vst)
	return cnt
ab = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]
for a, b in ab:
	L[a].append(b)
	L[b].append(a)

print(sum(dfs(b, a, b, set()) == 0 for a, b in ab))

Submission status: Accepted

Solution code:

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

ab = [tuple(map(int, input().split())) for i in range(m)]


def connected(E, n):
    V = {i: False for i in range(1, n+1)}
    V[1] = True
    
    queue = []
    queue.append(1)
    while queue:
        i = queue.pop()
        for (a, b) in E:
            if i == a and not V[b]:
                V[b] = True
                queue.append(b)
            if b == i and not V[a]:
                V[a] = True
                queue.append(a)

    for i, b in V.items():
        if not b:
            return False
    return True

def rest(E, e):
    xs = []
    for f in E:
        if f != e:
            xs.append(f)
    return xs


count = 0
for e in ab:
    F = rest(ab, e)
    if not connected(F, n):
        count += 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(100000)
 
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
graph = [[] for k in range(N)]
 
for _ in range(M):
    s, t = inpl()
    s, t = s-1, t-1
    graph[s].append(t)
    graph[t].append(s)
 
prenum = [-1] * N
lowest = [float("inf")] * N
found = [False] * N
parent = [-1] * N
 
result = set()
bridges = set()
root = 0

def DFS(i, cur, prev):
    global root
    prenum[i] = cur
    lowest[i] = cur
    found[i] = True
    parent[i] = prev 
    for p in graph[i]:
        if found[p]:
            if p != prev:
                lowest[i] = min(lowest[i], prenum[p])
        else:
            cur = DFS(p, cur+1, i)
            lowest[i] = min(lowest[i], lowest[p])
    if prenum[prev] <= lowest[i]:
        result.add(prev)    
     
    return cur
DFS(0, 1, -1)
 
if parent.count(0) <= 2:
    result = result.difference([0])

bridges = set()

for i in range(1, N):
    p = parent[i]
    if prenum[p] < lowest[i]:
        if p > i:
            p, i = i, p
        bridges.add((p, i))

print(len(bridges))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-       
import numpy as np
connected = 0

def dfs(graph, start, v, visited=None):
    if(visited==None):  visited = []
    visited.append(start)    
    if(len(visited)==v):
        global connected
        connected += 1
        return
    for Next in graph[start]:  
        if ( Next in visited ):  continue
        dfs(graph, Next, v, visited)
    return


v, e = map(int, input().split())
graph = np.zeros((e,2)).astype('uint16')

for i in range(e):
    graph[i] = list(map(int, input().split()))

lw = [[] for i in range(v)]
for path in graph:
    lw[path[0]-1].append(path[1]-1)
    lw[path[1]-1].append(path[0]-1)

for path in graph:
    lw[path[0]-1].remove(path[1]-1)
    lw[path[1]-1].remove(path[0]-1)
    dfs(lw,0,v)
    lw[path[0]-1].append(path[1]-1)
    lw[path[1]-1].append(path[0]-1)
print(e-connected)

Submission status: Accepted

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

g = {}
E = []
for _ in range(M):
    line = input().split(" ")
    a = line[0]
    b = line[1]
    E.append((a,b))
    if not a in g:
        g[a] = []
    g[a].append(b)

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

def judge(a, b):
    flags = {}
    for v in g:
        flags[v] = False
    q = [a]
    flags[a] = True
    while len(q)>0:
        v = q.pop(0)
        for u in g[v]:
            if (v==a and u==b) or (v==b and u==a):
                continue
            elif not flags[u]:
                flags[u] = True
                q.append(u)
    ret = True
    for v in flags:
        ret = ret and flags[v]

    return not ret

cnt = 0
for e in E:
    if judge(e[0],e[1]):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from copy import deepcopy

N,M  = [int(i) for i in input().split()]
ab   = [[int(i)-1 for i in input().split()] for j in range(M)]
edge = [[] for i in range(N)]
ans  = 0

for i in range(M):
        edge[ab[i][0]].append(ab[i][1])
        edge[ab[i][1]].append(ab[i][0])

def paint(tmpEdge):
        used=[False for i in range(N)]
        stack=[0]
        used[0]=True
        while len(stack)>0:
                now=stack[-1]
                stack.pop(-1)
                for nextP in tmpEdge[now]:
                        if used[nextP]==False:
                                used[nextP]=True
                                stack.append(nextP)

        #print(used)
        if False in used:
                return True
        else:
                return False

for i in range(M):
        tmpEdge=deepcopy(edge)
        tmpEdge[ab[i][0]].remove(ab[i][1])
        tmpEdge[ab[i][1]].remove(ab[i][0])
        if paint(tmpEdge):
                ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
E = [map(lambda v: int(v)-1, raw_input().split()) for i in range(M)]
ans = 0
for k in range(M):
    used = [False] * N
    used[0] = True
    que = [0]
    while que != []:
        s = que.pop(0)
        for i in range(M):
            if i != k:
                a, b = E[i]
                if (s == a) and not used[b]:
                    used[b] = True
                    que.append(b)
                elif (s == b) and not used[a]:
                    used[a] = True
                    que.append(a)
    ans += sum(used) < N
print ans

Submission status: Accepted

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

dotlist = [[] for i in range(N)]
sidlist = []
count = 0 

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

def check(anum,bnum,cnum):
    donedot[cnum-1] = True
    for i in dotlist[cnum - 1]: 
        if (anum == cnum and i == bnum) or (bnum == cnum and i == anum):
            pass
        elif donedot[i - 1] == False:
            check(anum,bnum,i)

donedot = None

for m in range(M):
    donedot = [False for i in range(N)]
    a,b = sidlist[m]
    check(a,b,1)
    TorF = True
    for i in donedot:
        TorF  = TorF and i
    if  not TorF:
        count += 1

print(count)

Submission status: Accepted

Solution code:
a,b=[int(i) for i in input().split()]

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

e=[]

for i in range(b):
    x0,y0=[int(i) for i in input().split()]
    x=x0-1
    y=y0-1
    e.append([x,y])
    n[x].append(y)
    n[y].append(x)


def loopn(j,x,y):
  s.append(j)
  for k in n[j]:
    if k not in s and not (j== x and k==y) and not(j== y and k==x):
      loopn(k,x,y)
x = 0

for i,j in e:
  s=[]

  loopn(j,i,j)
  if i not in s:
    x +=1 
print(x)

Submission status: Accepted

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

L = []

for _ in range(M):
    a, b = map(int, input().split())
    L.append((a, b))


def f(l):
    passed = {i:False for i in range(1, N+1)}
    q = collections.deque()
    q.append(1)

    while len(q) > 0:
        now = q.popleft()
        nodes = l[now]
        for n in nodes:
            if not passed[n]:
                passed[n] = True
                q.append(n)

    for v in passed.values():
        if not v:
            return False

    return True

count = 0

for i in range(M):
    l = {j:[] for j in range(1,N+1)}
    for j in range(M):
        if j != i:
            l[L[j][0]].append(L[j][1])
            l[L[j][1]].append(L[j][0])
    if not f(l):
        count += 1

print(count)

Submission status: Accepted

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

data = [0] * (N+1)
def root(i):
  if data[i] < 0:
    return i
  data[i] = root(data[i])
  return data[i]

def link(a, b):
  a = root(a)
  b = root(b)
  if a != b:
    if -data[a] > -data[b]:
      data[a] += data[b]
      data[b] = a
    else:
      data[b] += data[a]
      data[a] = b

for i in range(M):
  for x in range(N+1):
    data[x] = -1
  for j in range(M):
    if i == j: continue
    link( es[j][0], es[j][1])
  if root( es[i][0]) != root( es[i][1]):
    ans += 1
print(ans)

Submission status: Accepted

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

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

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

def dfs(u,count,p):
	pre[u] = count;
	low[u] = pre[u];
	for v in edges[u]:
		if pre[v] == -1:
			low[u] = min(low[u], dfs(v,count+1,u))
		else:
			if v == p:
				continue
			low[u] = min(low[u], low[v])
	return low[u]

count=0
dfs(0,count,-1)
res=0

for i in range(1,N):
#	print("low: ", low[i] , " pre: ", pre[i])
	res += (1 if low[i] == pre[i] else 0)

print(res)

Submission status: Accepted

Solution code:
inp = input().split(" ")
num_vertex = int(inp[0])
num_edge = int(inp[1])

visited = []
def _dfs(graph, start, end):
	neighbors = graph[start]
	for i in neighbors:
		if i == end:
			return True
		elif i not in visited:
			visited.append(i)
			found = _dfs(graph, i, end)
			if found:
				return found
	return False

def dfs(graph, start, end):
	global visited
	visited = []
	return _dfs(graph, start, end)

vertices = {}
edges = []
for i in range(num_vertex):
	vertices[i+1] = []

for i in range(num_edge):
	inp = input().split(" ")
	edge = list(map(int, inp))
	vertices[edge[0]].append(edge[1])
	vertices[edge[1]].append(edge[0])
	edges.append(edge)

bridges = 0
for edge in edges:
	v = vertices.copy()
	e0 = v[edge[0]].copy()
	e1 = v[edge[1]].copy()
	e0.remove(edge[1])
	e1.remove(edge[0])
	v[edge[0]] = e0
	v[edge[1]] = e1
	if not dfs(v, edge[0], edge[1]):
		bridges += 1
print(bridges)

Submission status: Accepted

Solution code:
from collections import deque
def is_bridge(start, nodes, edge_tuple, n):
    seen = set()
    queue = deque()

    queue.append(start)
    seen.add(start)
    while len(queue) > 0:
        head = queue.popleft()
        for child in nodes[head]:
            if child not in seen and not (  (child == edge_tuple[0] and head == edge_tuple[1]) or   (child == edge_tuple[1] and head == edge_tuple[0])):
                seen.add(child)
                queue.append(child)


    return len(seen) != n



line_one = raw_input().split()
n = int(line_one[0])
m = int(line_one[1])

nodes = {}
edges = []
rand_start = None

for i in range(m):
    line = raw_input().split()
    edge = (int(line[0]), int(line[1]))
    if rand_start is None:
        rand_start = edge[0]

    if edge[0] not in nodes:
        nodes[edge[0]] = []
    if edge[1] not in nodes:
        nodes[edge[1]] = []

    nodes[edge[0]].append(edge[1])
    nodes[edge[1]].append(edge[0])

    edges.append(edge)
count = 0
for edge in edges:
    if is_bridge(rand_start, nodes, edge, n):
        count += 1

print count

Submission status: Accepted

Solution code:
def f(a, b, nodes, visited):
    if (a in visited):
        return False
    if (a == b):
        return True
    visited.append(a)
    for e in nodes[a]:
        if (f(e, b, nodes, visited)):
            return True
    return False


def main():
    n, m = [int(x) for x in input().split(' ')]
    nodes = {}
    edges = []
    for _ in range(m):
        a, b = [int(x) for x in input().split(' ')]
        if (a in nodes):
            nodes[a].append(b)
        else:
            nodes[a] = [b]
        if (b in nodes):
            nodes[b].append(a)
        else:
            nodes[b] = [a]
        edges.append((a, b))
    ans = 0
    for a, b in edges:
        nodes[a] = [x for x in nodes[a] if x != b]
        nodes[b] = [x for x in nodes[b] if x != a]
        if (not f(a, b, nodes, [])):
            ans += 1
        nodes[a].append(b)
        nodes[b].append(a)
    print(ans)


main()

Submission status: Accepted

Solution code:
N, M = [int(a) for a in input().split()]
adj = [[False] * N for _ in range(N)]
edgelist = []
for i in range(M):
    a, b = [int(a) for a in input().split()]
    a-=1
    b-=1
    adj[a][b] = True
    adj[b][a] = True
    edgelist.append((a,b))

bridges = 0
for a,b in edgelist:
    adj[a][b] = False
    adj[b][a] = False

    marked = [False] * N
    stk = [a]
    while stk:
        x = stk.pop()
        marked[x] = True
        for i in range(N):
            if adj[x][i] and not marked[i]:
                stk.append(i)
    if not marked[b]:
        bridges += 1

    adj[a][b] = True
    adj[b][a] = True

print(bridges)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [[False]*n for i in range(n)]
hen_m = []
for i in range(m):
    x1, x2 = map(int, input().split())
    x1 -= 1
    x2 -= 1
    hen_m.append([x1, x2])
    a[x1][x2] = True
    a[x2][x1] = True
for i in range(n):
    a[i][i] = True

#ワーシャルフロイド
def warshall(n, c):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c[j][k] = c[j][k] or (c[j][i] and c[i][k])

ans = 0
# Mの辺を消して、わ～シャルフロイド
for i in range(m):
    b = [i[::] for i in a]
    x1 , x2 = hen_m[i]
    b[x1][x2] = False
    b[x2][x1] = False
    warshall(n, b)
    flag = 0
    for j in range(n - 1):
        for k in range(j + 1,n):
            if not b[j][k]:
                flag = 1
                break
        if flag == 1:
            break
    #print(i, flag)
    ans += flag
print(ans)