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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA), BridgeEdge(nodeB)]

class BridgeEdge:
    def __init__(self, node):
        self.node = node
        self.judge = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)


nodes = [Node(i) for i in range(N+1)]
bridges = []
for A, B in (map(int, input().split()) for _ in range(M)):
    b = Bridge(nodes[A], nodes[B])
    nodes[A].addEdge(b.edges[1])
    nodes[B].addEdge(b.edges[0])
    bridges.append(b)


s = [(None, nodes[1], 1)]
idx = 0
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1

    if level > N * 2:
        break

    for nxt in cur.bridges:
        if not pre is nxt.node and nxt.judge < 2:
            nxt.judge += 1
            s.append((cur, nxt.node, level+1))

cnt = 0
for bd in bridges:
    if sum(1 for b in bd.edges if b.judge <= 1) > 0:
        cnt += 1

print(cnt)

Solution (Python):
class UnionFind:
    def __init__(self, N):
        
        
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: 
            return v
        else:
            
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) 
        s2 = self.find(v) 
        
        if s1 == s2: 
            return False
        
        if self.rank[s1] > self.rank[s2]: 
            self.vertices[s1] += self.vertices[s2] 
            self.vertices[s2] = s1
        else: 
            self.vertices[s2] += self.vertices[s1] 
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, M = map(int, input().split())
E = []
for _ in range(M):
    a, b = map(int, input().split())
    E.append((a, b))
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    edges = [e for j, e in enumerate(E) if j != i]
    for a, b in edges:
        uf.union(a-1, b-1)
    if len([v for v in uf.vertices if v < 0]) >= 2:
        ans += 1
print(ans)

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

def check(v):
    c[v] = 1
    for i in range(len(lst2)):
        if lst2[i][0]-1 == v and c[lst2[i][1]-1] == 0 and d[i] == 0:
            d[i] = 1
            check(lst2[i][1]-1)
        if lst2[i][1]-1 == v and c[lst2[i][0]-1] == 0 and d[i] == 0:
            d[i] = 1
            check(lst2[i][0]-1)
    return
    
count = 0
for i in range(M): 
    c = [0] * N 
    d = [0]* (M-1) 
    lst2 = lst[:i] + lst[i+1:] 
    
    check(0) 
    if 0 in c:
        count += 1
    else:
        pass
    
print (count)

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 = map(int, input().split())  
edges = [list(map(int, input().split())) for i in range(m)]
ans = 0

for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i != j:
      uf.union(edges[j][0]-1, edges[j][1]-1)
      c = 0
  for j in range(n):
    if j == uf.find(j):
      c += 1
  if c > 1:
    ans += 1
print(ans)

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

def search(UF,loc):
    if UF[loc] == loc:
        return UF[loc]
    else:
        UF[loc] = search(UF,UF[loc])
        return UF[loc]
    

ans = 0

for i in range(m):
    aa,bb = AB[i]
    UF = [_ for _ in range(n+1)]
    for k in range(m):
        a,b = AB[k]
        if i!=k:
            UF[a] = search(UF,a)
            UF[b] = search(UF,b)
            if UF[a] != UF[b]:
                UF[max(UF[a],UF[b])] = UF[min(UF[a],UF[b])]
    for l in range(1,n+1):
        UF[l] = search(UF,l)
    for j in range(1,n):
        if UF[j] != UF[j+1]:
            ans += 1
            break
print(ans)

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

  def reset(self):
    self._parent=[n for n in range(0, n)]

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
ct=0
UF=UF(n)
for i in range(m):
  for j in range(m):
    if j!=i:
      UF.unite(l[j][0]-1,l[j][1]-1)
  if UF.groupnum()!=1:ct+=1
  UF.reset()
print(ct)

Solution (Python):
n,m=map(int,input().split())
g=[list() for _ in range(n+1)]
side=[list(map(int,input().split())) for i in range(m)]
for a,b in side:
	g[a].append(b)
	g[b].append(a)
cnt=0
def dfs(x,s):
	ed[x-1]=1
	for i in g[x]:
		if s!={x,i} and ed[i-1]==0:dfs(i,s)
cnt=0
for i in range(m):
	ed=[0]*n
	dfs(1,set(side[i]))
	if 0 in ed:cnt+=1
print(cnt)

Solution (Python):



from collections import deque

N, M = map(int, input().rstrip().split(' '))

edges = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().rstrip().split(' '))
    a -= 1
    b -= 1
    edges[a].append([b, i])
    edges[b].append([a, i])
    
count = 0
for i in range(M):
    v = [False] * N
    v[0] = True
    d = deque([0])
    while len(d) > 0:
        temp_v = d.popleft()
        for e in edges[temp_v]:
            if e[1] != i and v[e[0]] == False:
                d.append(e[0])
                v[e[0]] = True
            
    if sum(v) != N:
        count += 1
        
print(count)

Solution (Python):
n,m=map(int,input().split())
l=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
a=0
while 1:
    x=0
    for i in range(n):
        if len(l[i])==1:
            l[l[i][0]].remove(i)
            l[i]=[]
            x+=1
    if x==0:break
    a+=x
print(a)

Solution (Python):

import sys
sys.setrecursionlimit(300000)

def dfs(s, t, conn, visited):
    
    
    if s == t:
        return True
    visited[s] = True
    for n in conn[s]:
        if not visited[n] and dfs(n, t, conn, visited):
            return True
    return False


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    
    ret = 0
    for i in range(M):
        conn = [[] for _ in range(N)]
        for j in range(M):
            if i == j:
                continue
            conn[a[j] - 1].append(b[j] - 1)
            conn[b[j] - 1].append(a[j] - 1)
        visited = [False] * N
        if not dfs(a[i] - 1, b[i] - 1, conn, visited):
            
            
            ret += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
edges = []
for i in range(0, M):
	edges.append(list(map(int, input().split())))
cnt = 0
for i in range(0, M):
	grp = []
	for j in range(0, N):
		lst = []
		for k in range(0, N):
			lst.append(False)
		grp.append(lst)
	for j in range(0, M):
		if i != j:
			grp[edges[j][0]-1][edges[j][1]-1] = True
			grp[edges[j][1]-1][edges[j][0]-1] = True
	memo = []
	for j in range(0, N):
		memo.append(True)
	queue = [0]
	while queue != []:
		now = queue.pop(0)
		memo[now] = False
		if True not in memo:
			break
		for j in range(0, N):
			if grp[now][j] and memo[j]:
				queue.append(j)
	if True in memo: cnt += 1
print(cnt)

Solution (Python):
import copy

n,m=list(map(int,input().split()))
way=[[] for _ in range(n)]
edge=[]
for i in range(m):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    way[a].append(b)
    way[b].append(a)
    edge.append((a,b))
checked=[False]*n

new_way=[]

def searchWay(current,to):
    flg=False
    checked[current]=True
    for i in new_way[current]:
        if i == to:
            return True
        else:
            if not checked[i]:
                if searchWay(i,to):
                    flg=True
                    break
    return flg

ans=0
for i in edge:
    checked=[False]*n
    new_way=copy.deepcopy(way)
    new_way[i[0]].remove(i[1])
    new_way[i[1]].remove(i[0])
    if not searchWay(i[0],i[1]):
        ans+=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
edges=[list(map(int,input().split())) for i in range(M)]
ans=0
for x in edges:
    l=list(range(N))
    for y in edges:
        if y!=x:l=[l[y[0]-1] if l[i]==l[y[1]-1] else l[i] for i in range(N)]
    if len(set(l))!=1:ans+=1
print(ans)

Solution (Python):


LIM = 50

graph =[[False  for _  in range(LIM)] for _ in range(LIM)]
visited = [False  for _  in range(LIM)]
bridges = []


def search(num):
    visited[num] = True
    for i, temp in enumerate(graph[num]):
        if not temp:  
            continue
        if visited[i]:  
            continue
        search(i)


def do():
    ans = 0
    N ,M = list(map(int,input().split(" ")))
    for _ in range(M):
        a,b = list(map(int,input().split(" ")))
        a -= 1
        b -= 1

        bridges.append([a,b])
        graph[a][b] =  graph[b][a] = True
    for bridge in bridges: 
        graph[bridge[0]][bridge[1]] = graph[bridge[1]][bridge[0]] = False
        for j in range(LIM):
            visited[j] = False
        search(0) 
        flag = False

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





if __name__ == "__main__":
    do()

Solution (Python):
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
graph=list([0]*N for _ in range(N))
ans=0
for a,b in ab:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

def dfs(s):
    visited[s]=1
    for i in range(N):
        if graph[s][i] == 0 or visited[i] == 1:
            continue
        dfs(i)

for a,b in ab:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited=[0]*N
    dfs(0)
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
    if sum(visited)<N:
        ans+=1


print(ans)

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

graph = [[0] * N for _ in range(N)]
for a, b in edges:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1


def dfs(v):
    visited[v] = 1
    for v2 in range(N):
        if graph[v][v2]==0 or visited[v2]==1:
            continue
        dfs(v2)


ans = 0
for a, b in edges:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited = [0] * N

    dfs(0)

    bridge = 0
    if sum(visited) < N :
        bridge = 1
        ans+=1
        
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

print(ans)

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

graph = [[0] * N for _ in range(N)]
for a, b in edges:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1


def dfs(v):
    visited[v] = 1
    for v2 in range(N):
        if graph[v][v2]==0:
            continue
        if visited[v2]==1:
            continue
        dfs(v2)


ans = 0
for a, b in edges:
    graph[a - 1][b - 1] = 0
    graph[b - 1][a - 1] = 0
    visited = [0] * N

    dfs(0)
    

    bridge = 0
    for i in range(N):
        if visited[i] == 0:
            bridge = 1
    if bridge==1:
        ans += 1

    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

print(ans)

Solution (Python):
import sys
import itertools
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) for v in input().split()] for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)

ans = 0

for i in range(M):
    u = UnionFind(N)
    for j in range(M):
        if i != j:
            u.unite(L[j][0] - 1, L[j][1] - 1)

    for j in range(N - 1):
        if u.same(j, j + 1) == False:
            ans += 1
            break

print(ans)

Solution (Python):
N,M=map(int,input().split())
ab=[[] for i in range(N)]
AB=[]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    ab[a].append(b)
    ab[b].append(a)
    AB.append([a,b])
ans=0
for i in range(M):
    x,y=AB[i]
    ab[x].remove(y)
    ab[y].remove(x)
    stack=[i for i in ab[0]]
    reached=[0]*N
    reached[0]=1
    while(stack):
        b=stack.pop()
        if reached[b]==1:
            continue
        for k in ab[b]:
            stack.append(k)
        reached[b]=1
    ab[x].append(y)
    ab[y].append(x)
    if reached!=[1]*N:
        ans+=1
print(ans)

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

graph = [[False] * N for _ in range(N)]
for a, b in edges:
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True

def dfs(v):
    visited[v] = True
    for v2 in range(N):
        if not graph[v][v2]:
            continue
        if visited[v2]:
            continue
        dfs(v2)
    
ans = 0
for a, b in edges:
    graph[a - 1][b - 1] = False
    graph[b - 1][a - 1] = False
    visited = [False] * N
    
    dfs(0)
    
    
    bridge = False
    for i in range(N):
        if visited[i] == False:
            bridge = True
    if bridge:
        ans += 1
        
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True
    
print(ans)

Solution (Python):
n,m = map(int,input().split())
a,b,ans = [[] for _ in range(n)],[],0
def solve(v,aa,bb):
    visited[v] = True
    for n in a[v]:
        if not visited[n] and set([v,n]) != set([aa,bb]):
            solve(n,aa,bb)

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

for i in range(m):
    visited = [True]+[False]*(n-1)
    x,y = b[i]
    solve(0,x,y)
    if visited != [True]*n:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
lis = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    lis[a].append(b)
    lis[b].append(a)
counter = 0
flag = True
while flag:
    flag = False
    for index in range(1, N+1):
        if len(lis[index]) == 1:
            lis[lis[index][0]].remove(index)
            lis[index].pop(0)
            counter += 1
            flag = True
print(counter)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N,M=[int(val) for val in input().split()]
a=deque()
b=deque()

for i in range(M):
  x,y = (int(val) for val in input().split())
  a.append(x)
  b.append(y)

cnt=0
for j in range(M):
    
    val_a=a.popleft()
    val_b=b.popleft()

    stack=deque([1])
    visited=deque()

    while len(stack) > 0:
        val=stack.pop()
        if visited.count(val)==0:
            visited.append(val)
            for i in range(len(a)):
                if a[i]==val:
                    if b[i] != visited:
                        stack.append(b[i])
            for i in range(len(b)):
                if b[i]==val:
                    if a[i] != visited:
                        stack.append(a[i]) 
                        
    if len(visited) < N:
        cnt+=1
    
    a.append(val_a)
    b.append(val_b)

print(cnt)

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


def dfs(v):
    global visited
    visited[v] = 1
    for u in range(1, n + 1):
        global graph
        if u in graph[v] and visited[u] == 0:
            dfs(u)


def main():
    ans = m
    for i in range(m):
        global graph
        graph = [[] for _ in range(n + 1)]
        for j, e in enumerate(edge):
            if i == j:
                continue
            v, u = e
            graph[v].append(u)
            graph[u].append(v)
        global visited
        visited = [0] * (n + 1)
        dfs(1)
        if all(visited[1:]):
            ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def f(L,res):
    for i in range(1,N+1):
        
        if len(L[i]) == 1:
            L[L[i][0]].remove(i)
            L[i] = []
            res = f(L,res+1)
    return res


N,M = map(int,input().split())
L = [[] for _ in range(N+1)]

for i in range(M):
    a,b = map(int,input().split())
    L[a].append(b)
    L[b].append(a)
print(f(L,0))

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


parent = [i for i in range(N)]
rank = [0] * N


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


def same(x, y):
    return find(x) == find(y)


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1

num = 0
for a, b in S:
    parent = [i for i in range(N)]
    rank = [0] * N
    for c, d in S:
        if c == a and b == d:
            continue
        else:
            unite(c, d)

    flag = False
    for i in range(N):
        if flag:
            break
        for j in range(N):
            if not same(i, j):
                flag = True
                break

    if flag:
        num += 1


print(num)

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

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

cnt = 0
for i in range(M):
    un = UnionFind(N+1)
    for ind,x in enumerate(ab):
        if(ind!=i):
            un.unite(x[0],x[1])

    if(un.find(ab[i][0])!=un.find(ab[i][1])):
        cnt += 1
print(cnt)

Solution (Python):


import math
import sys


def check(route,N):
  dct = {i:[] for i in range(1,N+1)}
  for a,b in route:
    dct[a].append(b)
    dct[b].append(a)

  nxt = [1]
  visited = set()
  while len(nxt)>0 and len(visited)<N:
    p = nxt.pop(0)
    visited.add(p)
    for q in dct[p]:
      if q not in visited:
        nxt.append(q)      

  if len(visited)<N:
    return 1
  else:
    return 0


def main():
  
  N,M = map(int, input().split())
  route = []
  for _ in range(M):
    route.append(list(map(int, input().split())))

  
  ans = 0
  for i in range(M):
    ans += check(route[0:i]+route[i+1:], N)    
  return ans

if __name__ == "__main__":
  print(main())

Solution (Python):
import collections
v,e=map(int,input().split())
g=[list(map(int,input().split())) for _ in range(e)]
ans=0
for i in range(e):
  tmp=g[:i]+g[i+1:]
  ga=[[] for _ in range(v+1)]
  for j in range(e-1):
    s,t=tmp[j][0],tmp[j][1]
    ga[s].append(t)
    ga[t].append(s)
  visited=[0]*(v+1)
  queue=collections.deque([1])
  visited[1]=1
  while 1:
    if len(queue)==0:
      break
    tv=queue.popleft()
    for i in ga[tv]:
      if visited[i]==0:
        queue.append(i)
        visited[i]=1
  if visited.count(1)!=v:
    ans+=1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, M = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for _ in range(M)]

count = 0
for a, b in AB:
    uf = UnionFind(N + 1)
    for c, d in AB:
        if (a, b) == (c, d):
            continue
        uf.union(c, d)
    if uf.size(1) != N:
        count += 1

print(count)

Solution (Python):
from collections import deque as deque
def IsBridgeBFS(m):
    newlines=[[] for oiejfo in range(N)]
    for k,line in enumerate(lines):
        x,y=line
        if k==m:continue
        newlines[x].append(y)
        newlines[y].append(x)
    stack=deque()
    went=[False]*N
    stack.append(0)
    went[0]=True
    while stack:
        cur=stack.pop()
        for togo in newlines[cur]:
            if not went[togo]:
                went[togo]=True
                stack.append(togo)
    return(not all(went))

N,M=[int(k) for k in input().split()]
lines=[[int(j)-1 for j in input().split()]for i in range(M)]

print(sum([IsBridgeBFS(k) for k in range(M)]))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else: self.par[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

ans = 0
for i in range(M):
    path = UnionFind(N)
    for j in range(M):
        if j != i:
            path.union(a[j], b[j])
    flag = True
    for j in range(N):
        for k in range(j, N):
            if not path.same_check(j, k):
                flag = False
    if not flag:
        ans += 1

print(ans)

Solution (Python):

"""解説
Union-Find

i番目の辺(ai, bi)を除く全ての辺を使ってUnion-Find木を作る。

その後、ai と bi がつながっているかを判定する。つながっていないならば、ai,biの辺は橋である。

この操作をすべてのiにおいて全探索する。

【計算量】
たぶんO(M(N+M))

Union-Findによるあるノード(a, b)が同じグループかどうか（今回では、同じグループ＝繋がっている）
の判定は高速でできる。

"""
class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self.parent = [n for n in range(0, N)]
        
        self.depth = [1] * N

    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) 
        return self.parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return

        
        if self.depth[gx] < self.depth[gy]:
            self.parent[gx] = gy
        else:
            self.parent[gy] = gx
            if self.depth[gx] == self.depth[gy]: self.depth[gx] += 1

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)


def solve():
    N, M = list(map(int, input().split()))
    edges = []

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

    
    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, edge in enumerate(edges):
            if i == j: continue
            
            a, b = edge
            uf.unite(a, b)
        
        
        
        a, b = edges[i]
        if not uf.is_same_group(a, b): ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    solve()

Solution (Python):

"""解説
Union-Find

i番目の辺(ai, bi)を除く全ての辺を使ってUnion-Find木を作る。

その後、ai と bi がつながっているかを判定する。つながっていないならば、ai,biの辺は橋である。

この操作をすべてのiにおいて全探索する。

【計算量】
たぶんO(NM)

Union-Findによるあるノード(a, b)が同じグループかどうか（今回では、同じグループ＝繋がっている）
の判定は高速でできる。

"""
class UnionFind():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self.parent = [n for n in range(0, N)]
        
        self.depth = [1] * N

    def find(self, x):
        """ 木の根(どのグループか)を求める """
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]) 
        return self.parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return

        
        if self.depth[gx] < self.depth[gy]:
            self.parent[gx] = gy
        else:
            self.parent[gy] = gx
            if self.depth[gx] == self.depth[gy]: self.depth[gx] += 1

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find(x) == self.find(y)


def solve():
    N, M = list(map(int, input().split()))
    edges = []

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

    
    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j, edge in enumerate(edges):
            if i == j: continue
            
            a, b = edge
            uf.unite(a, b)
        
        
        
        a, b = edges[i]
        if not uf.is_same_group(a, b): ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    solve()

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

ab = {}
for a, b in AB:
	if not a in ab:
		ab[a] = [b]
	else:
		ab[a] += [b]
	if not b in ab:
		ab[b] = [a]
	else:
		ab[b] += [a]

def check():
	for i in ab:
		if 1 == len(ab[i]):
			return True
	else:
		return False

c = 0
while check():
	for p in ab:
		if 1 == len(ab[p]):
			c += 1
			ab[ab[p][0]].remove(p)
			del ab[p][0]

print(c)

Solution (Python):
def wf(this_graf):
    s = len(graf)
    for k in range(s):
        for i in range(s):
            for j in range(s):
                this_graf[i][j] = min(this_graf[i][j], this_graf[i][k] + this_graf[k][j])
    return this_graf

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graf = [[10 ** 10 for i in range(n)] for j in range(n)]

for i, j in ab:
    graf[i - 1][j - 1] = 1
    graf[j - 1][i - 1] = 1

import copy
cnt = 0

for i, j in ab:
    this_graf = copy.deepcopy(graf)
    tmp = 0
    this_graf[i - 1][j - 1] = 10 ** 10
    this_graf[j - 1][i - 1] = 10 ** 10
    this_graf = wf(this_graf)
    for i in range(n):
        for j in range(n):
            if this_graf[i][j] == 10 ** 10:
                tmp = 1
                break
        if tmp:
            break
    cnt += tmp

print(cnt)

Solution (Python):
def check(i,adj):
    visited = [False]*N
    visited[i] = True
    q = [i]
    while q != []:
        v = q.pop(0)
        for w in adj[v]:
            if not visited[w]:
                visited[w] = True
                q.append(w)
    return all(visited)
N,M = map(int,input().split())
adj = [[] for i in range(N)]
edges = []
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges.append((a,b))
    adj[a].append(b)
    adj[b].append(a)
ans = 0
for a,b in edges:
    tmp = [adj[i].copy() for i in range(N)]
    tmp[a].remove(b)
    tmp[b].remove(a)
    if not check(0,tmp):
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
	def __init__(self, n):
		self.graph = [i for i in range(n)]

	def find(self, n):
		if self.graph[n] == n:
			return n
		self.graph[n] = self.find(self.graph[n])
		return self.graph[n]

	def union(self, n, m):
		self.graph[self.find(self.graph[m])] = self.find(self.graph[n])

N,M=map(int, input().split())
bridge=[[int(x) for x in input().split()] for _ in range(M)]

ans=0

for j in range(M):
	uf = UnionFind(N+1)
	for i in range(M):
		if i == j:
			continue
		uf.union(*bridge[i])
	if len(set([uf.find(n) for n in range(1, N+1)])) > 1:
		ans += 1

print(ans)