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

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

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


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)

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

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

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

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

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

Solution (Python):


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

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

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

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

Solution (Python):
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=[] 
nodes=[[] for i in range (n)] 
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)

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

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

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

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