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.

Solution (Python):
n,m = map(int, raw_input().split(" "))
bridges = [[]]
check = [0]
needline = 0
for i in range(n):
    bridges.append([])
for t in range(m):
    x,y = map(int, raw_input().split(" "))
    bridges[x].append(y)
    bridges[y].append(x)




def recursivebridge(k,count,goal,checki):
    boo = False

    for h in bridges[k]:
        if count >= 2 and h == goal:
            boo = True
        elif h not in checki:
            checky = checki[:]
            checky.append(h)
            boo = boo or recursivebridge(h,count+1,goal,checky)
    return(boo)

for i in range(n+1):
    if i in check:
        continue
    checkcopy = check[:]
    checkcopy.append(i)
    if recursivebridge(i,0,i,checkcopy) is False:

        needline += 1


if needline > m:
    needline = m
print needline

Solution (Python):





from sys import stdin

def nReachable(node, edges):
  visited = []
  gray    = [node]
  while len(gray) > 0:
    n    = gray[0]
    gray = gray[1:]
    if n not in visited:
      visited.append(n)
      gray.extend([e[1] for e in edges if e[0] == n])
      gray.extend([e[0] for e in edges if e[1] == n])
  return len(visited)

def solve(N, E):
  cnt = 0
  for i in range(len(E)):
    EE = E[:i] + E[i + 1:]  
    if nReachable(1, EE) < N:
      cnt += 1
  return cnt

def splitIntoInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, M = splitIntoInt(stdin.readline())
E = []
for i in range(M):
  a, b = splitIntoInt(stdin.readline())
  E.append((a, b))
print(solve(N, E))

Solution (Python):

import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
INF = 10**100
r = range

class infix(object):
    def __init__(self, function):
        self.function = function

    def __ror__(self, other):
        self.left = other
        return self

    def __or__(self, other):
        return self.function(self.left, other)

    def __call__(self, value1, value2):
        return self.function(value1, value2)

@infix
def c(f_t_u, f_u_r): return lambda t: f_u_r(f_t_u(t))

class _Ap(object):
    def __rlshift__(self, other):
        self.value = other
        return self

    def __rshift__(self, other):
        return other(self.value)
Ap = _Ap()
A = Ap




n, m = map(int, input().split())
g = [set() for i in range(n+1)]
e = set();
for i in range(m):
    a,b=map(int,input().split())
    b<<A>>g[a].add
    a<<A>>g[b].add
    (a,b)<<A>>e.add

color = [0]*(n+1)
def dfs(u, p):

    color[u] = 1
    for next_u in g[u]:
        if next_u == p:
            continue
        if not color[next_u]:
            dfs(next_u, u)

ret = 0
for edge in e:
    color = [0]*(n+1)
    g[edge[0]].remove(edge[1]);
    g[edge[1]].remove(edge[0]);

    dfs(edge[0], -1)
    ret += color[edge[1]]
    g[edge[0]].add(edge[1]);
    g[edge[1]].add(edge[0]);

print(m-ret);

Solution (Python):

import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
INF = 10**100
r = range

class infix(object):
    def __init__(self, function):
        self.function = function

    def __ror__(self, other):
        self.left = other
        return self

    def __or__(self, other):
        return self.function(self.left, other)

    def __call__(self, value1, value2):
        return self.function(value1, value2)

@infix
def c(f_t_u, f_u_r): return lambda t: f_u_r(f_t_u(t))

class _Ap(object):
    def __rlshift__(self, other):
        self.value = other
        return self

    def __rshift__(self, other):
        return other(self.value)
Ap = _Ap()
A = Ap




n, m = map(int, input().split())
g = [set() for i in range(n+1)]
e = set();
for i in range(m):
    a,b=map(int,input().split())
    g[a].add(b);
    g[b].add(a);
    e.add((a,b))

color = [0]*(n+1)
def dfs(u, p):

    color[u] = 1
    for next_u in g[u]:
        if next_u == p:
            continue
        if not color[next_u]:
            dfs(next_u, u)

ret = 0
for edge in e:
    color = [0]*(n+1)
    g[edge[0]].remove(edge[1]);
    g[edge[1]].remove(edge[0]);

    dfs(edge[0], -1)
    ret += color[edge[1]]
    g[edge[0]].add(edge[1]);
    g[edge[1]].add(edge[0]);

print(m-ret);

Solution (Python):
n,m=[int(i) for i in input().split()]
pp=[[0 for i in range(2)] for j in range(m)]
not_bridge=0




def dfs(Graph, Start, Vn, Visited=None):
  

  if Graph[Start]==[] and Visited==None: 
        Next=Start+1        
        dfs(Graph, Next, Vn, Visited)  
  else:


    if (Visited==None):  Visited = [] 
    Visited.append(Start)  

    if len(Visited)==Vn: 
        global not_bridge
        not_bridge=not_bridge+1
    for Next in Graph[Start]:  
        if ( Next in Visited ):  continue  
        dfs(Graph, Next, Vn, Visited)  


for i in range(m) :
    pp[i] =[int(i) for i in input().split()]

for i in range(m) : 
    p=pp[:]
    del p[i]


    l = [[] for i in range(n+1)] 
    for pi in p:  
        l[pi[0]].append(pi[1])
        l[pi[1]].append(pi[0])

    
    
    dfs(l, 0, n)
    
print(m-not_bridge)

Solution (Python):
def dfs(num):
    global used, G
    used.add(num)
    for t in G[num]:
        if t not in used:
            dfs(t)

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

ans = 0
for a, b in es:
    G[a].remove(b)
    G[b].remove(a)
    used = set()
    dfs(0)
    if len(used) != N:
        ans += 1
    G[a].append(b)
    G[b].append(a)

print(ans)

Solution (Python):
n,m=[int(i) for i in input().split()]
pp=[[0 for i in range(2)] for j in range(m)]
ans=0




def dfs(Graph, Start, Vn, Visited=None):
  

  if Graph[Start]==[] and Visited==None: 
        Next=Start+1        
        dfs(Graph, Next, Vn, Visited)  
  else:

    if (Visited==None):  Visited = [] 
    Visited.append(Start)  


    if len(Visited)==Vn:
        global ans
        ans=ans+1
    for Next in Graph[Start]:  
        if ( Next in Visited ):  continue  
        dfs(Graph, Next, Vn, Visited)  


for i in range(m) :
    pp[i] =[int(i) for i in input().split()]

for i in range(m) : 
    p=pp[:]
    del p[i]


    l = [[] for i in range(n+1)] 
    for pi in p:  
        l[pi[0]].append(pi[1])
        l[pi[1]].append(pi[0])

    
    
    dfs(l, 0, n)

print(m-ans)

Solution (Python):

import copy

def bfs(n, ls, mat):
    tmat = copy.deepcopy(mat)
    cnt = 0
    for a, b in ls:
        tmat[a][b] = tmat[b][a] = 0
        visited = [0 for i in range(n+2)]
        que = [a]
        
        while que:
            st = que.pop(0)
            visited[st] = 1
            for i in range(1, n + 1):
                if tmat[st][i] == 1 and visited[i] != 1:
                    que.append(i)
                    
        tmat = copy.deepcopy(mat)
        if sum(visited) != n:
            cnt += 1
    return cnt

n, m = list(map(int, input().split()))
ls = []
for i in range(m):
    a, b = list(map(int, input().split()))
    ls.append((a, b))
    
mat = [[0 for i in range(m + 2)] for j in range(m + 2)]
for a, b in ls:
    mat[a][b] = mat[b][a] = 1
    
cnt = bfs(n, ls, mat)
print(cnt)

Solution (Python):



def dfs(s):
    global used, G
    used.add(s)
    for t in G[s]:
        if t not in used:
            dfs(t)

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

ans = 0
for a, b in es:
    G[a].remove(b)
    G[b].remove(a)
    used = set()
    dfs(0)
    if len(used) != N:
        ans += 1
    G[a].append(b)
    G[b].append(a)

print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**7)

def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0] * N]
    for _ in [0] * M:
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    bridges = len(get_lowlink(edges, M)[0])
    print(bridges)
 
"""
edge_numはedgeの数
"""
def get_lowlink(edges, edge_num):

 
    n = len(edges)
    order = [-1] * n
    low = [float("inf")] * n
    bridges = []
    articulations = [0] if edge_num == n-1 and len(edges[0]) > 1 else []
    append_bridge, append_articulation = bridges.append, articulations.append
 
    def dfs(v, prev, k):
        order[v] = low[v] = k
 
        is_articulation = False
        for dest in edges[v]:
            if order[dest] == -1:
                dfs(dest, v, k + 1)
                if low[v] > low[dest]:
                    low[v] = low[dest]
                if order[v] < low[dest]:
                    append_bridge((v, dest))
                is_articulation |= order[v] <= low[dest]
 
            elif dest != prev and low[v] > order[dest]:
                low[v] = order[dest]
 
        if v > 0 and is_articulation:
            append_articulation(v)
 
    dfs(0, 0, 0)
    return bridges, articulations
 
 
if __name__ == "__main__":
    solve()

Solution (Python):



def dfs(index, connects):
    global IS_VISITED

    
    
    

    if index in connects.keys():
        IS_VISITED[index] = True
        nodes = [x for x in connects[index]]
    else:
        return

    for node in nodes:
        if IS_VISITED[node] == False:
            dfs(node, connects)


def is_connected(inputs):
    global IS_VISITED

    connects = {}
    for edge in inputs:
        edge = [int(edge[0]), int(edge[1])]
        if edge[0] in connects.keys():
            connects[edge[0]].append(edge[1])
        else:
            connects[edge[0]] = [edge[1]]

        if edge[1] in connects.keys():
            connects[edge[1]].append(edge[0])
        else:
            connects[edge[1]] = [edge[0]]

    
    IS_VISITED = [True] + [False for x in range(int(N))]
    dfs(1, connects)
    return len(IS_VISITED) is not len([1 for idx in range(len(IS_VISITED)) if IS_VISITED[idx]])


N, _ = input().split(" ")

IS_VISITED = []

inputs = []
while True:
    try:
        inputs.append(input().split(" "))
    except EOFError:
        break


count = 0
for i in range(len(inputs)):
    
    if is_connected(inputs[:i] + inputs[i + 1:]):
        
        count += 1

print(count)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
e=[[0 for i in range(n)] for j in range(n)]
xx=[]
for i in range(m):
 x=i2()
 x[0]-=1
 x[1]-=1
 xx.append(x)
 e[x[0]][x[1]]=1
 e[x[1]][x[0]]=1
d=[0 for i in range(n)]
def dfs(v):
    d[v]=1
    for i in range(n):
        if e[v][i]==1 and d[i]==0:
            dfs(i)
a=0
for i in xx:
 e[i[0]][i[1]]=0
 e[i[1]][i[0]]=0
 dfs(0)
 if 0 in d:
   a+=1
 d=[0 for j in range(n)]
 e[i[0]][i[1]]=1
 e[i[1]][i[0]]=1
print(a)

Solution (Python):
N,M = map(int,input().split())
a=[0]*M
b=[0]*M
adj = [[0 for _ in range(N)] for _ in range(N)]
flag = [0]*N
bridge = 0

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

def dfs(cv):
    flag[cv-1]=1
    for i,x in enumerate(adj[cv-1]):
        if x==1 and flag[i]==0 :
            dfs(i+1)
    return

for i in range(M):
    flag=[0]*N
    adj[a[i]-1][b[i]-1] = adj[b[i]-1][a[i]-1] = 0
    dfs(1)
    if sum(flag)<N:
        bridge+=1
    adj[a[i]-1][b[i]-1] = adj[b[i]-1][a[i]-1] = 1

print(bridge)

Solution (Python):
def dfs(p, reached):
    global N, G
    reached.append(p)
    for i in range(N):
        if G[p][i] and i not in reached:
            reached = dfs(i, reached[:])
    return reached

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

ans = 0
for i in range(N):
    for j in range(i):
        if G[i][j]:
            G[i][j] = False
            G[j][i] = False
            if len(dfs(0, [])) < N:
                ans += 1
            G[i][j] = True
            G[j][i] = True

print(ans)

Solution (Python):
import sys

numBridge = 0
visited = set()

def singletonSet(x):
    r = set()
    r.add(x)
    return r

def dfs(start, stack):

    global numBridge

    visited.add(start)
    tree[start] = []
    for v in nbr[start]:

        if v in done[start]:
            pass
        else:
            done[v].add(start)
            tree[start].append(v)
            if v in visited:

                loop[start].add(v)
                while not v in stack:
                    w = revtree[v]
                    loop[w].add(v)
                    v = w
                t = v

                v = start
                while v != t:
                    w = revtree[v]
                    loop[w].add(v)
                    v = w
            else:
                revtree[v] = start
                dfs(v, stack.union(singletonSet(start)))

def count():
    c = 0
    for p in range(1, n + 1):


        c += len(tree[p]) - len(loop[p])
    return c

f = sys.stdin
n, m = map(int, next(f).rstrip().split(' '))
nbr     = [[]    for _ in range(n + 1)]
tree    = [[]    for _ in range(n + 1)]
done    = [set() for _ in range(n + 1)]
revtree = [None  for _ in range(n + 1)]
loop    = [set() for _ in range(n + 1)]
for line in f:
    (p, q) = map(int, line.rstrip().split(' '))

    nbr[p].append(q)
    nbr[q].append(p)

dfs(1, set())
print(count())

Solution (Python):


visited = []

def dfs(adjacent_matrix, current_node, num_nodes):
    for next_node in range(num_nodes):
        if adjacent_matrix[current_node][next_node] == False:
            continue
        if visited[next_node] == True:
            continue
        visited[next_node] = True
        dfs(adjacent_matrix, next_node, num_nodes)

def main():
    num_nodes, num_edges = map(int, input().split(" "))
    
    edges = []
    for _ in range(num_edges):
        start_node, end_node = map(int, input().split(" "))
        edges.append([start_node - 1, end_node - 1])

    adjacent_matrix = [[False for _ in range(num_nodes)] for _ in range(num_nodes)]
    for e in edges:
        adjacent_matrix[e[0]][e[1]] = adjacent_matrix[e[1]][e[0]] = True

    num_bridges = 0
    global visited
    visited = [False] * num_nodes
    for e in edges:
        adjacent_matrix[e[0]][e[1]] = adjacent_matrix[e[1]][e[0]] = False

        dfs(adjacent_matrix, 0, num_nodes)
        
        is_connected = True
        for v in visited:
            if v == False:
                is_connected = False
        
        for i in range(num_nodes):
            visited[i] = False

        if is_connected == False:
            num_bridges += 1

        adjacent_matrix[e[0]][e[1]] = adjacent_matrix[e[1]][e[0]] = True

    print(num_bridges)

if __name__ == '__main__':
    main()

Solution (Python):
def dfs(x):
    visited[x] = True
    for x2 in xrange(n):
        if graph[x][x2] == False: continue
        if visited[x2] == True: continue
        dfs(x2)

def main():
    global n, m, graph, visited

    n, m = map(int, raw_input().split())
    graph = [[False for _ in xrange(n)] for _ in xrange(n)]
    ai = []
    bi = []
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ai.append(a)
        bi.append(b)
        graph[a][b] = graph[b][a] = True
    ans = 0

    for i in xrange(m):
        graph[ai[i]][bi[i]] = graph[bi[i]][ai[i]] = False
        visited = [False for _ in xrange(n)]
        bridge = True

        dfs(0)
        if all(visited): bridge = False
        if bridge: ans += 1
        graph[ai[i]][bi[i]] = graph[bi[i]][ai[i]] = True

    print ans
    return 0

if __name__ == '__main__':
    main()

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

h=[]
for i in range(N+1):
	h.append([])

a=[]
b=[]

for i in range(M):
	A, B = map(int, input().split())		
	h[A].append(B)
	h[B].append(A)
	a.append(A)
	b.append(B)




def dfs(Graph, Start, Visited=None):
	if(Visited==None): Visited = []
	Visited.append(Start)
	
	for Next in Graph[Start]:
		if( Next in Visited ): 
			
			continue
		dfs(Graph, Next, Visited)

z=[_ for _ in range(1, N+1)]

ans=0

import copy
for i in range(M):
	g = copy.deepcopy(h)
	
	A = a[i]
	B = b[i]

	g[A].remove(B)
	g[B].remove(A)
	
	Visited = []
	dfs(g, 1, Visited)
	
	
	if len( list(set(z) - set(Visited)) ) > 0:
	    ans += 1

	
print(ans)

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

Solution (Python):


NM = list(map(int, input().split()))
N = NM[0]
M = NM[1]

edges = [None] * M

for i in range(M):
    ab = list(map(int, input().split()))
    edges[i] = (ab[0], ab[1])

passed = [1]
queue = [1]
def search(edges, s):
    queue.pop(0)
    for i in range(M - 1):
        
        if (len(passed) == N):
            break
        if (edges[i][0] == s and not edges[i][1] in passed):
            passed.append(edges[i][1])
            queue.append(edges[i][1])
        if (edges[i][1] == s and not edges[i][0] in passed):
            passed.append(edges[i][0])
            queue.append(edges[i][0])
    if(len(passed) != N and queue != []):
        search(edges, queue[0])

edges_save = edges[:]

counter = 0
for i in range(M):
    passed = [1]
    queue = [1]
    edges = edges_save[:]
    edges.pop(i)
    search(edges, 1)
    if(len(passed) != N):
        counter += 1

print(counter)

Solution (Python):
visitted = []

def dfs(matrix, num_nodes, current_node):
    global visited

    for next_node in range(num_nodes):
        if matrix[current_node][next_node] == False:
            continue
        elif visited[next_node] == True:
            continue
        else:
            visited[next_node] = True
            dfs(matrix, num_nodes, next_node)

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

    adjacent_matrix = [[False for _ in range(N)] for _ in range(N)]
    edges = []
    for _ in range(M):
        node1, node2 = map(int, input().split(" "))
        edges.append([node1 - 1, node2 - 1])
        adjacent_matrix[node1 - 1][node2 - 1] = adjacent_matrix[node2 - 1][node1 -1] = True

    global visited
    visited = [False] * N

    num_bridges = 0
    for e in edges:
        adjacent_matrix[e[0]][e[1]] = adjacent_matrix[e[1]][e[0]] = False

        dfs(adjacent_matrix, N, 0)

        is_connected = True
        for v in visited:
            if v == False:
                is_connected = False
                break

        if is_connected == False:
            num_bridges += 1

        for i in range(N):
            visited[i] = False

        adjacent_matrix[e[0]][e[1]] = adjacent_matrix[e[1]][e[0]] = True

    print(num_bridges)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict

n, m = map(int, input().split())
br = []
r = defaultdict(list)
for _ in range(m):
    a, b = input().split()
    br.append((a, b))
    r[a].append(b)
    r[b].append(a)

done = {}

def s(node):
    if done[node] == 1:
        return
    done[node] = 1
    for i in r[node]:
        if node in down and i in down:
            continue
        s(i)

def chk():
    for i in r.keys():
        done[i] = 0
    s('1')
    for i in done.keys():
        if done[i] == 0:
            return False
    return True

nbr = 0
for i in br:
    down = i
    if chk() == False:
        nbr += 1

print(nbr)

Solution (Python):


n, m = list(map(int, input().split()))
br = []
r = {}
for i in range(m):
    a, b = input().split()
    br.append((a, b))
    try:
        r[a].append(b)
    except KeyError:
        r[a] = []
        r[a].append(b)
    try:
        r[b].append(a)
    except KeyError:
        r[b] = []
        r[b].append(a)

done = {}

def s(node):
    if done[node] == 1:
        return
    done[node] = 1
    for i in r[node]:
        if node in down and i in down:
            continue
        s(i)

def chk():
    for i in r.keys():
        done[i] = 0
    s('1')
    for i in done.keys():
        if done[i] == 0:
            return False
    return True

nbr = 0
for i in br:
    down = i
    if chk() == False:
        nbr += 1

print(nbr)

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

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

    
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
        return

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

res = 0

for i in range(M):
    G = UnionFind(N)
    for j in range(M):
        if i != j:
            G.union(A[j],B[j])
    minas = 0
    for k in G.table:
        if k < 0:
            minas += 1
    if minas == 1:
        res += 1


print(M-res)

Solution (Python):




"""
Created on Mon Oct  9 22:12:40 2017

@author: kitagenbakurou
"""
import numpy as np
import copy

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

mp_moto = np.zeros((N , N))  

s_list = []
for i in range(M) : 
    s = input().split()
    s = [int(k) for k in s]
    mp_moto[s[0] - 1 , s[1] - 1] = 1
    mp_moto[s[1] - 1 , s[0] - 1] = 1
    s_list.append(s)

def df(x) : 
    visited[x] = 1
    for i in range(N) : 
        go = mp[x , i]
        if go == 0 : continue
        elif visited[i] == 1 : continue
        else : 
            df(i)

cnt = 0
for i in range(M) : 
    visited = np.zeros(N)
    mp = copy.deepcopy(mp_moto)
    
    s = s_list[i]
    mp[s[0] - 1 , s[1] - 1] = 0
    mp[s[1] - 1 , s[0] - 1] = 0
    df(0)
    if sum(visited) != N : cnt += 1

print(cnt)

Solution (Python):
def root(uf,i):
    if uf[i] == i:
        return i
    else:
        uf[i] = root(uf,uf[i])
        return uf[i]

n,m = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(m)]
ctr = 0
for i in edge:
    uf = [i for i in range(n+1)]
    for j in edge:
        if i==j: continue
        x = root(uf,j[0])
        y = root(uf,j[1])
        uf[x] = y
    for j in range(1,n+1):
        root(uf,j)
    for j in range(1,n):
        if uf[j] != uf[j+1]:
            break
    else:
        ctr += 1
print(m-ctr)

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

g=[[False for i in range(N)] for j in range(N)]
ab=[()]*M
v=[False]*N

def dfs(n):
    v[n]=True
    for i in range(N):
        if g[n][i]==True and v[i]==False:
            dfs(i)

for i in range(M):
    a,b=map(int,raw_input().split(' '))
    a-=1
    b-=1
    g[a][b]=g[b][a]=True
    ab[i]=(a,b)

ans=0
for i in range(M):
    a,b=ab[i]
    g[a][b]=g[b][a]=False

    dfs(0)

    if v!=[True]*N:
        ans+=1

    g[a][b]=g[b][a]=True
    v=[False]*N

print ans

Solution (Python):



def _p(*obj):
    if "DEBUG" not in globals():
        return
    import inspect
    l = inspect.stack()[1].lineno
    print("[{}]: ".format(l), end='')
    from pprint import pprint
    pprint(*obj)


def isConnected(edges):
    _p(edges)
    nodes_from = []
    for n in range(N):
        nodes_from.append(
            [e[1] if e[0] == n else e[0] for e in edges if n in e]
        )
    _p(nodes_from)

    visited_nodes = set()
    next_nodes = set([0])
    while len(next_nodes) != 0:
        visited_nodes |= set(next_nodes)
        new_next_nodes = set()
        for n in next_nodes:
            new_next_nodes |= set(nodes_from[n])
        next_nodes = new_next_nodes - visited_nodes
    _p(visited_nodes)
    return len(visited_nodes) == N


def main():
    global N, M
    N, M = [int(i) for i in input().split()]
    edges = []
    for m in range(M):
        edges.append([int(i) - 1 for i in input().split()])

    count = 0
    for m in range(M):
        es = edges[:]
        es.pop(m)
        if not isConnected(es):
            count += 1
    print(count)


if __name__ == "__main__":
    main()

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

visited = None
def dfs(v):
    visited[v] = True
    for u,e in enumerate(G[v]):
        if e == 0 or visited[u] == True: continue
        dfs(u)

ans = []
for i in range(N):
    for j in range(i+1, N):
        if G[i][j] is 0:continue
        G[i][j] = G[j][i] = 0
        visited = [False] * N
        dfs(0)
        G[i][j] = G[j][i] = 1
        if not all(visited):ans.append(i)

print(len(ans))

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

global N, M, graph, visited
N, M = [int(i) for i in input().split()]
graph = [[False for _ in range(50)] for _ in range(50)]
visited = [False for _ in range(50)] 
a = [0 for _ in range(50)]
b = [0 for _ in range(50)]
for i in range(M):
    a[i], b[i] = [int(i) for i in input().split()]
    a[i] -= 1
    b[i] -= 1
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = True
    
ans = 0
for i in range(M):
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = False
    for j in range(N):
        visited[j] = False
    dfs(0)

    bridge = False
    for j in range(N):
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = True
print(ans)

Solution (Python):
n, m = map(int, input().split())
hen = []
for _ in range(m):
    hen.append(list(map(int, input().split())))

def dfs(vis, graph, x, n):
    vis[x] = True
    for i in range(n):
        if graph[x][i] == False:
            continue
        if vis[i] == True:
            continue
        dfs(vis, graph, i, n)
    return vis


ans = 0
for i in range(m):
    graph = [[False for _ in range(n)] for _ in range(n)]
    rng = [a for a in range(m)]
    del rng[i]
    for y in rng:
        graph[hen[y][0]-1][hen[y][1]-1] = True
        graph[hen[y][1]-1][hen[y][0]-1] = True
    vis = [False for _ in range(n)]
    vis = dfs(vis, graph, 0, n)
    connected = True
    for k in range(n):
        if vis[k] == False:
            connected = False
    if connected == False:
        ans += 1

print(ans)

Solution (Python):
def main():
    global N, graph, vis
    N, M = map(int, input().split())
    AB = {tuple(map(int, input().split())) for _ in [0] * M}

    graph = [[False for _ in [0] * N] for _ in [0] * N]
    for a, b in AB:
        graph[a-1][b-1] = graph[b-1][a-1] = True

    ans = 0
    for a, b in AB:
        graph[a-1][b-1] = graph[b-1][a-1] = False
        vis = [False] * N
        dfs(0)

        connected = True
        for i in range(N):
            if not vis[i]:
                connected = False
        if not connected:
            ans += 1
        graph[a-1][b-1] = graph[b-1][a-1] = True

    print(ans)

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

main()

Solution (Python):
from collections import deque

def read():
    return [int(i) for i in input().split()]

visited = []

def bfs(e, G):
    """ 連結じゃなければtrue. """
    n = len(G)
    visited = [False for i in range(n)]
    q = deque([0])
    visited[0] = True

    while len(q) > 0:
        cur = q.popleft()
        for dst in G[cur]:
            if sorted([cur,dst]) == sorted(e):
                continue
            if visited[dst]:
                continue
            q.append(dst)
            visited[dst] = True
    
    return sum(visited) != n


def main():
    n, m = read()
    G = [[] for j in range(n)]
    edge = []
    for i in range(m):
        a, b = read()
        a -= 1; b -= 1
        edge.append([a,b])
        G[a].append(b)
        G[b].append(a)

    cnt = 0
    for e in edge:
        cnt += bfs(e,G)
    print(cnt)

main()

Solution (Python):
import copy


def main():
    """
    自己ループを含まない
    二重辺を含まない: 点AからBへの辺は１つ(以下)
    連結グラフ：任意の点から任意の点に移動できる

    ある辺を取り除くと非連結になる場合、その辺を橋という
    →橋がなくなるとたどり着けない

    N: <=50
    M: <= 50

    ある辺を取り除いてすべてのノードにたどり着けるか
    すべてのノードを列挙する
    ノードを辿ってみる（探索アルゴリズム）
    たどれたらたどれたノードをため込む
    終わったら列挙したノードと比較して同じならOK
    """
    N, M = map(int, input().split())
    e = set()
    for _ in range(M):
        a, b = map(int, input().split())
        e.add((a, b))

    ans = 0
    for k in e:
        searched = set()
        e_copy = copy.deepcopy(e)
        e_copy.remove(k)

        def dfs(v1):
            searched.add(v1)
            for v2 in range(1, N + 1):
                if v2 in searched:
                    continue
                if (v1, v2) in e_copy or \
                        (v2, v1) in e_copy:
                    dfs(v2)

        dfs(1)
        if len(searched) < N:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def solution():
	n,m = [int(x) for x in input().split(' ')]
	e = []
	ans = 0 

	for i in range(m):
		_x,_y = [int(x) for x in input().split(' ')]
		e.append((_x-1,_y-1))

	for i in range(m):
		matrix = []
		for _i in range(n):
				matrix.append([-1]*n)
		for _i in range(m):
			if _i != i: 
				_e = e[_i]
				matrix[_e[0]][_e[1]]  = 1
				matrix[_e[1]][_e[0]]  = 1

		for k in range(n):
			for _i in range(n):
				for _j in range(n):
					if _i!=_j:
						if matrix[_i][k] >0 and matrix[k][_j] > 0:
							if matrix[_i][_j]>0:
								matrix[_i][_j] = min(matrix[_i][_j],matrix[_i][k]+matrix[k][_j])
							else:
								matrix[_i][_j] = matrix[_i][k]+matrix[k][_j]
		isconnected = True
		for _i in range(n):
			if not(isconnected):
				break			
			for _j in range(n):
				if _i == _j:
					continue
				if matrix[_i][_j] == -1:
					isconnected = False
					ans+=1
					break

	print(ans)



solution()