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


import sys
sys.setrecursionlimit(10000)


class EndLoop(Exception):
    pass


def debug_print(L):
    for col in L:
        print(col)


def debug_print_joined(L):
    for col in L:
        print("".join(col))


def transpose_matrix(L):
    transposed = list(map(list, zip(*L)))
    return transposed


def solve():
    N, M = list(map(int, input().split(" ")))
    graph = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split(" ")))
        graph[a - 1][b - 1], graph[b - 1][a - 1] = 1, 1

    visited = [False for _ in range(N)]
    cnt = 0
    def dfs(v, G):
        visited[v] = True
        for v2 in range(N):
            if G[v][v2] == 1 and visited[v2] != True:
                dfs(v2, G)

    check = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if check[i][j] == True:
                pass
            elif graph[i][j] == 1 and check[i][j] == False:
                graph[i][j], graph[j][i] = 0, 0
                dfs(0, graph)
                if visited.count(False) == 0:
                    pass
                else:
                    cnt += 1
                graph[i][j], graph[j][i] = 1, 1
                visited = [False for _ in range(N)]
                check[i][j], check[j][i] = True, True

    print(cnt)
    

solve()

Solution (Python):


import sys
import os
import math
import itertools
import numpy as np
from collections import OrderedDict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
sys.setrecursionlimit(10000)


class EndLoop(Exception):
    pass


def debug_print(L):
    for col in L:
        print(col)


def debug_print_joined(L):
    for col in L:
        print("".join(col))


def transpose_matrix(L):
    transposed = list(map(list, zip(*L)))
    return transposed


def solve():
    N, M = list(map(int, input().split(" ")))
    graph = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split(" ")))
        graph[a - 1][b - 1], graph[b - 1][a - 1] = 1, 1

    visited = [False for _ in range(N)]
    cnt = 0
    def dfs(v, G):
        visited[v] = True
        for v2 in range(N):
            if G[v][v2] == 1 and visited[v2] != True:
                dfs(v2, G)

    check = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if check[i][j] == True:
                pass
            elif graph[i][j] == 1 and check[i][j] == False:
                graph[i][j], graph[j][i] = 0, 0
                dfs(0, graph)
                if visited.count(False) == 0:
                    pass
                else:
                    cnt += 1
                graph[i][j], graph[j][i] = 1, 1
                visited = [False for _ in range(N)]
                check[i][j], check[j][i] = True, True

    print(cnt)
    

solve()

Solution (Python):


import sys
import os
import math
import itertools
import numpy as np
from collections import OrderedDict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
sys.setrecursionlimit(10000)


class EndLoop(Exception):
    pass


def debug_print(L):
    for col in L:
        print(col)


def debug_print_joined(L):
    for col in L:
        print("".join(col))


def transpose_matrix(L):
    transposed = list(map(list, zip(*L)))
    return transposed


def solve():
    N, M = list(map(int, input().split(" ")))
    graph = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split(" ")))
        graph[a - 1][b - 1], graph[b - 1][a - 1] = 1, 1

    visited = [False for _ in range(N)]
    cnt = 0
    def dfs(v, G):
        visited[v] = True
        for v2 in range(N):
            if G[v][v2] == False:
                continue
            if visited[v2] == True:
                continue
            dfs(v2, G)

    check = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if check[i][j] == True:
                pass
            elif graph[i][j] == 1 and check[i][j] == False:
                graph[i][j], graph[j][i] = 0, 0
                dfs(0, graph)
                if visited.count(False) == 0:
                    pass
                else:
                    cnt += 1
                graph[i][j], graph[j][i] = 1, 1
                visited = [False for _ in range(N)]
                check[i][j], check[j][i] = True, True

    print(cnt)

    
solve()

Solution (Python):
N, M = map(int, input().split())
visited = [False for i in range(N)]
matrix = [[False for i in range(N)] for j in range(N)]
a = []
b = []
def dfs(v):
    visited[v] = True
    for v2 in range(N):
        if matrix[v][v2] == False:
            continue
        if visited[v2] == True:
            continue
        dfs(v2)
for i in range(M):
    _a, _b = map(int, input().split())
    a.append(_a - 1)
    b.append(_b - 1)
    matrix[a[i]][b[i]] = True
    matrix[b[i]][a[i]] = True
ans = 0
for i in range(M):
    matrix[a[i]][b[i]] = False
    matrix[b[i]][a[i]] = False

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

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

print(ans)

Solution (Python):
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)]
    a = [0 for _ in range(M)]
    b = [0 for _ in range(M)]  
    for i in range(M):
        a[i] = E[i][0] - 1
        b[i] = E[i][1] - 1
        adjacent[a[i]][b[i]] = True
        adjacent[b[i]][a[i]] = True

    
    
    ans = 0
    visited = [False for _ in range(N)]
    for i in range(M):
        
        adjacent[a[i]][b[i]] = False
        adjacent[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
        adjacent[a[i]][b[i]] = True
        adjacent[b[i]][a[i]] = 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))

Solution (Python):


import sys
from collections import defaultdict


def check(graph, edge):
    checked = set()
    checking = set([edge[0]])
    while True:
        for p in checking - checked:
            if p == edge[0] and edge[1] in graph[p]:
                checked.add(p)
                checking.update(graph[p] - set([edge[1]]))
                continue

            if edge[1] in graph[p]:
                return True

            checked.add(p)
            checking.update(graph[p])

        if checking - checked == set():
            break

    return False


def main():
    m, n = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]
    graph = defaultdict(set)
    edges = []
    for line in sys.stdin:
        x, y = line.rstrip().split(" ")
        graph[x].add(y)
        graph[y].add(x)
        edges.append((x, y))

    count = 0
    for edge in edges:
        if not check(graph, edge):
            count += 1

    print(count)


if __name__ == "__main__":
    main()

Solution (Python):

N,M=list(map(int,raw_input().split()))

nl=[[0]*(N+1) for i in range(N+1)]
a=[0]*M
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x][y]=1
	nl[y][x]=1
	a[i]=[x,y]	



def dfs(v,p):
	
	F[v]=1
	for j in range(N+1):
		
		if nl[v][j]!=0 and F[j]==0:
			
			
			dfs(j,v)



c_graph=[1]*(N+1)
c_graph[0]=0



cnt=0

for i in range(M):
	F=[0]*(N+1)
	x=a[i][0]
	y=a[i][1]
	nl[x][y]=0
	nl[y][x]=0
	
	dfs(1,-1)
	
	if F!=c_graph:
		
		cnt+=1
	
	nl[x][y]=1
	nl[y][x]=1

print cnt

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

def dfs(Graph, Start, Visited=None):
    if (Visited==None):  Visited = []
    Visited.append(Start) 
    for Next in Graph[Start]: 
        if ( Next in Visited ):  
            continue 
        Visited = dfs(Graph, Next, Visited)
    return Visited
 
ans = 0
for it in range(M):
    hoge = list(ab)
    del hoge[it]
    l = [[] for i in range(N)]
    for pi in hoge:
        l[pi[0]-1].append(pi[1]-1)
        l[pi[1]-1].append(pi[0]-1)
    if(N != len(dfs(l, 0))):
        ans += 1
        
print(ans)

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


def DFS(table):
    visited = [1]
    que = [1]
    
    while que != []:
        now = que[0]
        del que[0]
        
        for index, e in enumerate(table[now]):
            if (e == 1) & (index not in visited):
                visited.append(index)
                que.append(index)
        
    if len(visited) == N:
        return 0
    else:
        return 1

ans = 0
for i in range(M):
    graph = AB.copy()
    del graph[i]
    
    table = [[0]*(N+1) for i in range(N+1)]
    for a,b in graph:
        table[a][b] = 1
        table[b][a] = 1

    ans += DFS(table)

print(ans)

Solution (Python):
import numpy as np
 
N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = M
for i in range(M):
  C = set()
  D = set()
  count = 0
  while(True):
    for j in range(M):
      if not i == j:
        if(count == 0):
          C.add(a[j]) 
          C.add(b[j])
          count += 1  
        if a[j] in C or b[j] in C:
          C.add(a[j])
          C.add(b[j])
    if(C == D):
      break
    else:
      D = C.union(D)
  if(len(C) == N):
    ans -= 1
print(ans)

Solution (Python):
from collections import defaultdict

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

Solution (Python):
import sys

class Node:
    def __init__(self, node_num):
        self.node_num = node_num
        self.connect = []
    def add_node(self, node):
        self.connect.append(node)
    def delete_node(self, node):
        self.connect.remove(node)

def is_connect(node_list):
    check_list = [0]
    stack = [node_list[0]]
    while len(stack) != 0:
        if len(check_list) == N:
            return True
        current = stack.pop()
        for ii in current.connect:
            if ii not in check_list:
                check_list.append(ii)
                stack.append(node_list[ii])
    return (len(check_list) == N)
        
N, M = list(map(int, sys.stdin.readline().strip().split(" ")))
node_list = [Node(i) for i in range(N)]
edge_list = []

for i in range(M):
    n, m = list(map(int, sys.stdin.readline().strip().split(" ")))
    node_list[n - 1].add_node(m - 1)
    node_list[m - 1].add_node(n - 1)
    edge_list.append((n-1, m-1))
    
res = 0
prev_edge = None
for e in edge_list:
    if prev_edge is not None:
        node_list[prev_edge[0]].add_node(prev_edge[1])
        node_list[prev_edge[1]].add_node(prev_edge[0])
    prev_edge = e
    node_list[e[0]].delete_node(e[1])
    node_list[e[1]].delete_node(e[0])
    if not is_connect(node_list):
        res += 1

print(str(res))

Solution (Python):
N, M = list(map(int, input().split()))
dic = {n + 1:set() for n in range(N)}

for m in range(M):
    a, b = list(map(int, input().split()))
    dic[a].add(b)
    dic[b].add(a)

def check(a, b):
    Sa = dic[a] - {b}
    stack = list(Sa)
    al = {a}
    while stack != []:
        p = stack.pop()
        al.add(p)
        stack += list(dic[p] - al)
        if b in stack:
            return False
    return True

res = 0
for n in range(1,N+1):
    S = dic[n]
    if len(S) == 1:
        res += 1
        dic[S.pop()].discard(n)
        continue
    elif len(S) == 0:
        continue
    else:
        for s in S:
            if check(n, s):
                res += 1
                dic[s].discard(n)
                continue

print(res)

Solution (Python):
import numpy as np

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 = map(int,input().split())

V = np.zeros((M,2))
for i in range(M):
    V[i,0], V[i,1] = map(int,input().split())

V = V.astype(np.int)

count = M
for i in range(M):
    mat = np.identity(N, dtype=np.int)
    for j in range(M):
        if i != j:
            mat[V[j,0]-1, V[j,1]-1] = 1
            mat[V[j,1]-1, V[j,0]-1] = 1
    if is_connected(mat):
        count -= 1


print(count)

Solution (Python):


bridges = 0

def visit(i, cnt, frm):
    global bridges

    cnt += 1

    pre[i] = cnt
    low[i] = cnt

    for n in e[i]:
        if pre[n] == -1:
            low[i] = min(low[i], visit(n, cnt, i))
            if low[n] == pre[n]:
                bridges += 1
        elif n != frm:
            low[i] = min(low[i], low[n])

    return low[i]

n, m = [int(x) for x in input().split()]
e = [set() for _ in range(n)]
for _ in range(m):
    p, q = [int(x) - 1 for x in input().split()]
    e[p].add(q)
    e[q].add(p)

pre = [-1 for _ in range(n)]
low = [-1 for _ in range(n)]

visit(0, 0, -1)
print(bridges)

Solution (Python):
import copy
N, M = map(int, input().split())
l = list()
m_list = []
for i in range(N):
    l.append([])
for i in range(M):
    a, b = map(int, input().split())
    m_list.append([a-1, b-1])
    l[a-1].append(b-1)
    l[b-1].append(a-1)

def f(l, s, e):
    m = [False] * len(l)
    m[s] = True
    q = []
    for nn in l[s]:
        q.append(nn)
        m[nn] = True
    while len(q) > 0:
        n = q[-1]
        q = q[:-1]
        for nn in l[n]:
            if m[nn] == False:
                m[nn] = True
                q.append(nn)
    return m[e]

sum = 0
for m in m_list:
    new_l = copy.deepcopy(l)
    new_l[m[0]].remove(m[1])
    new_l[m[1]].remove(m[0])
    if not f(new_l, m[0], m[1]):
        sum = sum + 1
print(sum)

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

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

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








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



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

    if not can(nb):
        
        count += 1

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

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

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

Solution (Python):

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

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

Solution (Python):

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)

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

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

Solution (Python):
def dfs(v, p, a):
    global ans
    
    
    
    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)

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

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

Solution (Python):


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)

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

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

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