Problem:


Score : 300 points

Problem Statement

You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges.

The i-th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i.  

An edge whose removal disconnects the graph is called a bridge.

Find the number of the edges that are bridges among the M edges.  

Notes

A self-loop is an edge i such that a_i=b_i (1 \leq i \leq M).

Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j (1 \leq i<j \leq M).

An undirected graph is said to be connected when there exists a path between every pair of vertices.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq min(N(N−1)⁄2,50)

1 \leq a_i<b_i \leq N

The given graph does not contain self-loops and double edges.

The given graph is connected.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M

Output

Print the number of the edges that are bridges among the M edges.

Sample Input 1

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

Sample Output 1

4

The figure below shows the given graph:

The edges shown in red are bridges. There are four of them.

Sample Input 2

3 3
1 2
1 3
2 3

Sample Output 2

0

It is possible that there is no bridge.

Sample Input 3

6 5
1 2
2 3
3 4
4 5
5 6

Sample Output 3

5

It is possible that every edge is a bridge.



Sample input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7


Sample output:
4

Submission status: Accepted

Solution code:
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
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def dfs(i, g, used, ng):
    for j in g[i]:
        if not used[j]:
            if (i, j) == ng or (j, i) == ng:
                continue
            used[j] = True
            dfs(j, g, used, ng)


def main():
    N, M = map(int, input().split())
    g = defaultdict(list)
    edges = []
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        g[a].append(b)
        g[b].append(a)
        edges.append((a, b))

    ans = 0
    for edge in edges:
        used = [False] * N
        used[0] = True
        dfs(0, g, used, edge)
        if False in used:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(num):  # 深さ優先探索
    used.append(num)
    for t in adj[num]:
        if t not in used:
            dfs(t)


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

adj = [[] for i in range(n)]  # G[i]は、頂点iと隣接する頂点
edges = []

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

ans = 0
for a, b in edges:
    # a-b感の辺を取り除く
    adj[a].remove(b)
    adj[b].remove(a)

    used = []
    dfs(0)  # 頂点1から（どこからでもいい）、接続している点を埋め尽くす
    if len(used) != n:
        ans += 1
    adj[a].append(b)
    adj[b].append(a)

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
ans=0
for i in range(M):
    init(N)
    for j in range(M):
        if i==j:
            continue
        unite(a[j],b[j])
    flag=0
    for j in range(1,N):
        if find(0)!=find(j):
            flag=1
            break
    if flag==1:
        ans+=1
print(ans)

Submission status: Accepted

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


def reach(cur, par, goal):
    if cur == goal:
        return True
    if used[cur]:
        return False
    used[cur] = True
    for e in edge[cur]:
        if e == par:
            continue
        if reach(e, cur, goal):
            used[cur] = False
            return True
    used[cur] = False
    return False


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

counter = 0
for i in range(n):
    for e in edge[i]:
        if not reach(i, e, e):
            counter += 1

print(counter // 2)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
ans=0
for i in range(M):
    init(N)
    for j in range(M):
        if i==j:
            continue
        unite(a[j],b[j])
    flag=0
    for j in range(N):
        for k in range(N):
            if find(j)!=find(k):
                flag=1
                break
        if flag==1:
            break
    if flag==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
G = defaultdict(list)
s = []
for i in range(m):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
    s.append((a - 1, b - 1))


def dfs(cur, pre, NG, k):
    global used
    used[cur] = 1
    for v in G[cur]:
        if v != pre and used[v] != 1 and (v, cur) != NG and (cur, v) != NG:
            dfs(v, cur, NG, k + 1)


num = 0
for i in range(m):
    ng = s[i]
    used = [0] * n
    used[0] = 1
    dfs(0, -1, ng, 0)
    if sum(used) == n:
        num += 1

print(m - num)

Submission status: Accepted

Solution code:
def dfs(now):
    if vis[now]:
        return 0
    vis[now]=1
    for i in range(n):
        if graph[now][i]:
            dfs(i)
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
vis=[0]*n
ans=0
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=0
    graph[edge[i][1]-1][edge[i][0]-1]=0
    vis=[0]*n
    dfs(0)
    connect=False
    for j in range(n):
        if vis[j]==0:
            connect=True
    if connect:
        ans+=1
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1

print(ans)

Submission status: Accepted

Solution code:
# cook your dish here
n, m = map(int, input().split(" "))
a = [list(map(int, input().split(" "))) for i in range(m)]
 
a_connects = [[] for i in range(n)]
for x, y in a:
	a_connects[x-1].append(y-1)
	a_connects[y-1].append(x-1)

jkl = []
for i in range(n):
    jkl.append(1)#if 1 ; mada

def ss(n): #jkl[n]
    jkl[n] = 0
    for x in a_connects[n]:
        if jkl[x] != 0:
            ss(x)
ass = 0            
for i in range(m):
    a_connects[a[i][0]-1].remove(a[i][1]-1)
    a_connects[a[i][1]-1].remove(a[i][0]-1)
    ss(0)
    if sum(jkl) != 0:
        ass += 1
    a_connects[a[i][0]-1].append(a[i][1]-1)
    a_connects[a[i][1]-1].append(a[i][0]-1)
    jkl = []
    for i in range(n):
        jkl.append(1)
print(ass)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(" "))
a = [list(map(int, input().split(" "))) for i in range(m)]

a_connects = [[] for i in range(n)]
for x, y in a:
	a_connects[x-1].append(y-1)
	a_connects[y-1].append(x-1)

#print(a_connects)

a_connect_sums = [len(connect) for connect in a_connects]

#print(a_connect_sums)

bridge_count = 0
while 1 in a_connect_sums:
	x = a_connect_sums.index(1)
	y = a_connects[x][0]
 
	a_connects[x].remove(y)
	a_connects[y].remove(x)
 
	a_connect_sums[x] -= 1
	a_connect_sums[y] -= 1
 
	bridge_count += 1
	#print('')
	#print(a_connects)
	#print(a_connect_sums)
 
print(bridge_count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())

# 0-indexed
visited = [False]*n
aa = []
bb = []
edge = []
for i in range(51):
    edge.append([False]*51)
"""
edge = [[False]*7]*7
"""

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    aa.append(a)
    bb.append(b)
    edge[a][b] = True
    edge[b][a] = True
    """
    for l in edge:
        print(l)
    print('')
    """

def dfs(vertex):
    visited[vertex] = True
    for i in range(n):
        if edge[vertex][i] and not visited[i]:
            #print(i, end=' ')
            dfs(i)

res = 0
for i in range(m):
    visited = [False]*n
    edge[aa[i]][bb[i]] = False
    edge[bb[i]][aa[i]] = False
    dfs(0)
    if not visited==[True]*n:
        res += 1
    #print(visited)
    edge[aa[i]][bb[i]] = True
    edge[bb[i]][aa[i]] = True

print(res)

Submission status: Accepted

Solution code:
class UFT(object):
    def __init__(self,N):
        self.par={i:i for i in range(1,N+1)}
        self.h={i:0 for i in range(1,N+1)}
    def find(self,n):
        if self.par[n]==n:
            return n
        else:
            self.par[n]=self.find(self.par[n])
            return self.par[n]
    def unite(self,a,b):
        a=self.find(a)
        b=self.find(b)
        if self.h[a]>self.h[b]:
            self.par[b]=a
        else:
            self.par[a]=b
            self.h[a]+=1
    def issame(self,a,b):
        return self.find(a)==self.find(b)

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
s=0

for i in range(m):
  obj=UFT(n)
  for (j,k) in enumerate(l):
    if i!=j:
      a,b=k
      obj.unite(a,b)
  a,b=l[i]
  if not obj.issame(a,b):s+=1

print(s)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

# 全体のグラフ作成
N,M = map(int, input().split())
adj_list = [[] for _ in range(N)]
AB = [tuple(map(int, input().split())) for _ in range(M)]

for a,b in AB:
    a -= 1
    b -= 1
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))

INF = float("inf")
ans = 0

# 1辺を除いてダイクストラ
for a,b in AB:
    a -= 1
    b -= 1
    
    adj_list[a].remove((1,b))
    adj_list[b].remove((1,a))
    
    dist = dijkstra(adj_list, N, 0)
    
    if INF in dist:
        ans += 1
        
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


def Find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def Unite(x,y):	#xとyを繋げる
	x = Find(x)
	y = Find(y)

	if x == y:
		return

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

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False

N,M = inpl()

lines = [inpl() for i in range(M)]
ans = 0
for j in range(M):
	table = [_ for _ in range(N+1)]
	rank  = [1 for _ in range(N+1)]
	for i in range(M):
		if i == j:
			continue
		x,y = lines[i]
		Unite(x,y)
	x,y = lines[j]

	if not Check(x,y):
		ans += 1

print(ans)

Submission status: Accepted

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

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

def isConnected(a, b):
    used = [0] * N
    def dfs(pos, pre):
        if used[pos]:
            return
        
        used[pos] = 1
        for to in range(N):
            if (pos == a and to == b) or (pos == b and to == a) or (G[pos][to] == 0):
                continue
            dfs(to, pos)
    dfs(0, -1)
    return used.count(1) != N

ans = 0
for a in range(N):
    for b in range(a+1, N):
        if G[a][b] == 0:
            continue
        ans = ans + isConnected(a, b)
    
print (ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(" "))
a = [list(map(int, input().split(" "))) for i in range(m)]

a_connects = [[] for i in range(n)]
for x, y in a:
	a_connects[x-1].append(y-1)
	a_connects[y-1].append(x-1)

a_connect_sums = [len(connect) for connect in a_connects]
bridge_count = 0
while 1 in a_connect_sums:
	x = a_connect_sums.index(1)
	y = a_connects[x][0]

	a_connects[x].remove(y)
	a_connects[y].remove(x)

	a_connect_sums[x] -= 1
	a_connect_sums[y] -= 1

	bridge_count += 1

print(bridge_count)

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-

class UnionFind:
    def __init__(self, n):
    # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.parent = [i for i in range(n + 1)]
    # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)
    #検索
    def find(self, x):
    #根ならその番号を返す
        if self.parent[x] == x:
            return x
        else:
    # 走査していく過程で親を書き換える
            self.parent[x] = self.find(self.parent[x])
            return self.find(self.parent[x])
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    #併合
    def unite(self, x, y):
    #根を探す
        x = self.find(x)
        y = self.find(y)
    # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
    # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

def main():

    n, m = map(int, input().split())
    es = []

    for _ in range(m):
        a, b = map(int, input().split())
        es.append((a, b))
        
    ans = 0
    for i in range(m):
        u = UnionFind(n)
        for j, e in enumerate(es):
            if j != i:
                a, b = e
                u.unite(a, b)
        a, b = es[i]
        if not u.same_check(a, b):
            ans += 1
    
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map( int, input().split())
V = [set([]) for _ in range(N)]
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append([a-1,b-1])
    V[a-1].add(b-1)
    V[b-1].add(a-1)
ans = 0
def conn(a,b,V):
    TV = [ False for _ in range(N)]
    TV[a] = True
    S = []
    for v in V[a]:
        if v != b:
            S.append(v)
    while len(S) != 0:
        c = S.pop()
        for w in V[c]:
            if TV[w] == False:
                TV[w] = True
                S.append(w)
    return TV
for e in E:
    a, b = e[0], e[1]
    comp = conn(a,b,V)
    if comp[b] == False:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
'''
ABC 075
https://www.youtube.com/watch?v=VJntQuR2zNI

'''
def inpl(): return input().split()
def arr(r, c): return [[False for x in range(c)] for y in range(r)]

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

if __name__ == '__main__':
    n, m = map(int, inpl())
    M = [list(map(int, inpl())) for _ in range(m)]

    ans = 0
    for e in range(m):#e:取り除く辺    
        graph = arr(n, n)#arr(i, j): i, j間に辺があればTrue
        for i in range(m):
            if i == e:
                continue
            a, b = M[i]
            #inputは1インデックス
            #graphは0インデックスなので、1減
            graph[a - 1][b - 1] = True
            graph[b - 1][a - 1] = True

        vis = [False for _ in range(n)]#訪れていたらTrue
        dfs(0)#0から辿れる範囲をvis = Trueにする
        
        connected = True
        for i in range(n):
            if not vis[i]:
                connected = False
                break
        if not connected:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
def bfs(branch,n):
	arrival = [0 for i in range(n+1)]
	q = [1]
	arrival[q[0]]=1
	while len(q) >= 1:
		for k in range(len(branch[q[0]])):
			if arrival[branch[q[0]][k]] == 0:
				arrival[branch[q[0]][k]] = arrival[q[0]] + 1
				q.append(branch[q[0]][k])
		q.pop(0)
	return arrival

n,m = map(int,input().split())
branch = dict()
for i in range(1,n+1):
    branch[i] = []
pair = []
for i in range(m):
    a,b = map(int,input().split())
    pair.append([a,b])
    branch[a].append(b)
    branch[b].append(a)
counter = 0

for i in range(m):
    branch[pair[i][0]].remove(pair[i][1])
    branch[pair[i][1]].remove(pair[i][0])
    arrival = bfs(branch,n)
    check = True
    for k in range(1,n+1):
        if arrival[k] == 0:
            check = False
    if check:
        counter += 1
    branch[pair[i][0]].append(pair[i][1])
    branch[pair[i][1]].append(pair[i][0])
print(m-counter)

Submission status: Accepted

Solution code:
class DFS:
    def __init__(self, N):
        self.N = N
        self.visited = [False for i in range(N)]
        self.graph = [[False for i in range(N)] for j in range(N)]

    def dfs(self, v):
        self.visited[v] = True
        for i in range(self.N):
            if (self.graph[v][i] == False):
                continue
            if (self.visited[i]):
                continue
            self.dfs(i)


N,M = map(int, input().split())
a = []
b = []
dfs = DFS(N)

for i in range(M):
    x,y = map(int, input().split())
    a.append(x-1)
    b.append(y-1)
    dfs.graph[a[i]][b[i]] = True
    dfs.graph[b[i]][a[i]] = True
ans = 0
for i in range(M):

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
f, t = [], []

for i in range(M) :
    a, b = map(int, input().split())
    
    f.append(a)
    t.append(b)
    
def get_root(idx) :
    if idx == u[idx] :
        return idx
    else :
        u[idx] = get_root(u[idx])
        return u[idx]
    
def union(a, b) :
    if get_root(a) <= get_root(b) :
        u[get_root(b)] = get_root(a)
    else :
        u[get_root(a)] = get_root(b)
cnt = 0 

for i in range(M) :
    u = [x for x in range(N)]
    
    for j in range(M) :
        if i != j :
            union(f[j] - 1, t[j] - 1)
    
    u_sets = set()
    for j in range(N) :
        u_sets.add(get_root(j))
        
    # print("DBG : ", u_sets)
    if len(list(u_sets)) != 1 :
        cnt += 1
        
print(cnt)

Submission status: Accepted

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

a = []
for i in range(m):
    a.append(list(map(int,input().split())))

b = [[0 for i in range(n)] for j in range(n)]

for i in a:
    b[i[1]-1][i[0]-1] = 1
    b[i[0]-1][i[1]-1] = 1
c = [sum(b[i]) for i in range(n)]
ans = 0
while 1 in c:
    d = c.index(1)
    e = b[d].index(1)
    b[e][d] = 0
    b[d][e] = 0
    c = [sum(b[i]) for i in range(n)]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
graph = defaultdict(list)
e = [tuple(map(int, input().split())) for i in range(m)]
for a, b in e:
  graph[a].append(b)
  graph[b].append(a)

used_v = [False for i in range(n+1)]
used_e = [[False for i in range(n+1)] for i in range(n+1)]
ord_ = [float("INF") for i in range(n+1)]
lowlink = [float("INF") for i in range(n+1)]

def dfs(v, k):
  used_v[v] = True
  ord_[v], lowlink[v] = k, k
  k += 1
  for to in graph[v]:
    if not used_v[to]:
      used_e[v][to] = True
      dfs(to, k)
      lowlink[v] = min(lowlink[v], lowlink[to])
    elif not used_e[to][v]:
      lowlink[v] = min(lowlink[v], ord_[to])

dfs(1, 0)
ans = 0
for a, b in e:
  if ord_[a]<lowlink[b] or ord_[b]<lowlink[a]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
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,raw_input().split())

edges = [map(int,raw_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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ft = [[int(i) -1 for i in input().split()] for _ in range(m)]
def dfs(f,n):

    visited[n] = True


    for value in renketu[n]:
        if value == f:
            continue
        if visited[value] == True:
            continue
        
        dfs(n,value)

    return
    

total = 0

for i in range(m):

    visited = [False for _ in range(n)]

    tmp = ft.pop(i)

    renketu = [[] for _ in range(n)]

    for value in ft:
        f,t = value
        renketu[f].append(t)
        renketu[t].append(f)

    dfs(0,0)
    
    
    if visited.count(True) != n:
        total += 1
    ft.insert(i,tmp)

print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

# 入力値の頂点ペア(辺)を格納する配列
a = [0] * 50
b = [0] * 50
# 頂点ペアが隣接しているかどうかを格納する配列
graph = [[False for i in range(50)] for j in range(50)]
# ある頂点が訪問済かどうかを格納する配列
visited = [False] * N

# 入力値の頂点ペア(辺)を格納していくループ
for i in range(M):
    a[i], b[i] = map(int, input().split())
    # 添字に合わせて入力値から1減らしておく
    a[i] -= 1
    b[i] -= 1
    # 入力値の内容に合わせて、隣接していることを記録
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

# 連結かどうか(全ての頂点が訪問済かどうか)を判定するDFS
def dfs(v):
    # 関数内で使用する変数のglobal宣言
    global graph
    global visited
    # 通った頂点は訪問済にする
    visited[v] = True
    for v2 in range(N):
        # 隣接していないor訪問済はやる意味ないのでcontinue
        if graph[v][v2] == False or visited[v2] == True:
            continue
        # 調べる必要のある箇所は再帰的に調べていく
        dfs(v2)

ans = 0
# 各辺について、橋かどうかを判定していくループ
for i in range(M):
    # まず該当の辺を外す(この状態で連結ではなくなってしまえばそれは橋)
    graph[a[i]][b[i]] = False
    graph[b[i]][a[i]] = False
    # 訪問済判定を初期化
    for j in range(N):
        visited[j] = False
    # 連結かどうか(全ての頂点が訪問済かどうか)を判定するDFS
    dfs(0)
    # 各頂点について、訪問済かどうかを確認していく
    bridge = False
    for j in range(N):
        # 頂点で一つでも未訪問の箇所があれば橋と判定する
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1
    # 外した辺を元に戻す
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

# 入力値の頂点ペア(辺)を格納する配列
a = [0] * 50
b = [0] * 50
# 頂点ペアが隣接しているかどうかを格納する配列
graph = [[False for i in range(50)] for j in range(50)]
# ある頂点が訪問済かどうかを格納する配列
visited = [False] * N

# 入力値の頂点ペア(辺)を格納していくループ
for i in range(M):
    a[i], b[i] = map(int, input().split())
    # 添字に合わせて入力値から1減らしておく
    a[i] -= 1
    b[i] -= 1
    # 入力値の内容に合わせて、隣接していることを記録
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

# 連結かどうか(全ての頂点が訪問済かどうか)を判定するDFS
def dfs(v):
    # 関数内で使用する変数のglobal宣言
    global graph
    global visited
    # 訪問済はやる意味ないのでreturn
    if visited[v]:
        return
    # 通った頂点は訪問済にする
    visited[v] = True
    for v2 in range(N):
        # 隣接している箇所は調べる
        if graph[v][v2]:
            # 調べる必要のある箇所は再帰的に調べていく
            dfs(v2)

ans = 0
# 各辺について、橋かどうかを判定していくループ
for i in range(M):
    # まず該当の辺を外す(この状態で連結ではなくなってしまえばそれは橋)
    graph[a[i]][b[i]] = False
    graph[b[i]][a[i]] = False
    # 訪問済判定を初期化
    for j in range(N):
        visited[j] = False
    # 連結かどうか(全ての頂点が訪問済かどうか)を判定するDFS
    dfs(0)
    # 各頂点について、訪問済かどうかを確認していく
    bridge = False
    for j in range(N):
        # 頂点で一つでも未訪問の箇所があれば橋と判定する
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1
    # 外した辺を元に戻す
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)

Submission status: Accepted

Solution code:
n=input().split()
rap=int(n[0])
sap=int(n[1])
map=[]
hap=[[] for i in range(1,rap+1)]
count=0
visited=[0 for i in range(1,1+rap)]
for i in range(sap):
    knight=input().split()
    morn=int(knight[0])-1
    after=int(knight[1])-1
    hap[morn].append(after)
    hap[after].append(morn)
    map.append([morn,after])
def dfs(u):
    visited[u]=1
    for v in king[u]:
        if visited[v]==0:
            dfs(v)
for j in range(sap):
    king=hap.copy()
    visited=[0 for i in range(1,rap+1)]
    king[map[j][0]].remove(map[j][1])
    king[map[j][1]].remove(map[j][0])
    dfs(map[j][0])
    king[map[j][0]].append(map[j][1])
    king[map[j][1]].append(map[j][0])
    sum=0
    for i in range(len(visited)):
        sum+=visited[i]
    if sum<rap:
        count+=1
print(count)

Submission status: Accepted

Solution code:
x=input().split()
n=int(x[0])
m=int(x[1])
adj=[[] for i in range(n)]
inp=[[0]*2 for i in range(m)]
count=0
visited=[False for i in range(n)]
def dfs(u):
    visited[u]=True
    for v in adj[u]:
        if not visited[v-1]:
            dfs(v-1)
for i in range(m):
    x=input().split()
    a=int(x[0])
    b=int(x[1])
    inp[i][0]=a
    inp[i][1]=b
ind=0
for i in inp:
    visited=[False for ii in range(n)]
    adj=[[] for iii in range(n)]
    inp[ind]=[]
    for j in inp:
        if j!=[]:
            adj[j[0]-1].append(j[1])
            adj[j[1]-1].append(j[0])
    
    dfs(0)
    for k in visited:
        if k==False:
            count+=1
            break
    inp[ind]=i
    ind+=1
print(count)

Submission status: Accepted

Solution code:
N,M = [int(x) for x in str(input()).split()]
E=[]
for i in range(M):
  E.append([int(x) for x in str(input()).split()])


def dfs(u):
  visited[u]=True
  for j in adj[u]:
    if visited[j]==False:
      dfs(j)

count=0
for i in range(M):
  P=E[:i]+E[i+1:]
  visited=[False for x in range(0,N+1)]
  adj=[[0] for k in range(0,N+1)]
  for j in range(1,N+1):
    r=[]
    for l in P:
      if l[0]==j:
        r.append(l[1])
      elif l[1]==j:
        r.append(l[0])
    adj[j]=r
  dfs(1)
  if sum(visited)!=N:
    count+=1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
es = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
gr = [[] for i in range(N)]
for i,(a,b) in enumerate(es):
    gr[a].append((b,i))
    gr[b].append((a,i))

ans = 0
for i in range(M):
    visited = [0] * N
    stack = [0]
    while stack:
        v = stack.pop()
        visited[v] = 1
        for to,e in gr[v]:
            if visited[to]: continue
            if i==e: continue
            stack.append(to)
    if sum(visited) < N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
links = {}
linkList = []
for i in range(M):
    a,b=map(int,input().split())
    linkList.append((a,b))
    if a not in links:
        links[a] = [b]
    else:
        links[a].append(b)
    if b not in links:
        links[b] = [a]
    else:
        links[b].append(a)
ans = 0
for a,b in linkList:
    links[a].remove(b)
    links[b].remove(a)
    visited = set()
    queue = deque()
    queue.appendleft(1)
    while queue:
        v = queue.pop()
        for w in links[v]:
            if w not in visited:
                queue.appendleft(w)
                visited.add(w)
    if len(visited) != N:
        ans += 1
    links[a].append(b)
    links[b].append(a)
print(ans)

Submission status: Accepted

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

def root(val):
    if parent[val]==val:
        return val
    else:
        parent[val]=root(parent[val])
        return parent[val]

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

def unite(x,y):
    xr=root(x)
    yr=root(y)
    if xr==yr :return
    if rank[xr]<rank[yr]:
        parent[xr]=yr
    else:
        parent[yr]=xr
        if rank[xr]==rank[yr]:
            rank[xr]+=1
ct=0
for i in range(M):
    parent=list(range(N))
    rank = [0]*N
    for a,b in (ab[:i]+ab[i+1:]):
        unite(a-1,b-1)
    for j in range(1,N):
        if not same(0,j):
            ct+=1
            break
print(ct)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
ab=[list(map(int,input().split())) for i in range(m)]

from pprint import pprint

l=[[False for _ in range(n)] for _ in range(n)]
v=[True for _ in range(n)]
for a,b in ab:
    l[b-1][a-1], l[a-1][b-1]=True,True
def dfs(x,t,v,j,m,n):
    j+=1
    if j<n+m:
        v[x]=False
        for i in range(1,n):
            if v[i]:
                if t[x][i]:
                    dfs(i,t,v,j,m,n)
import copy

ans=0
for i in range(m):
    j=0
    t=copy.deepcopy(l)
    t[ab[i][1]-1][ab[i][0]-1],t[ab[i][0]-1][ab[i][1]-1]=False,False
    v=[True for _ in range(n)]
    dfs(0, t, v, j, m,n)
        
    z=False
    for x in v:
        if x:
            z=True
    if z:
        ans+=1
print(ans)