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:
# -*- coding: utf-8 -*-

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

edges = [None] * M

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

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

edges_save = edges[:]

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

print(counter)

Submission status: Accepted

Solution code:
visitted = []

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

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

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

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

    global visited
    visited = [False] * N

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

        dfs(adjacent_matrix, N, 0)

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

        if is_connected == False:
            num_bridges += 1

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

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

    print(num_bridges)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
from collections import defaultdict

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

done = {}

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

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

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

print(nbr)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

done = {}

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

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

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

print(nbr)

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:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        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:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return

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

res = 0

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


print(M-res)

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Oct  9 22:12:40 2017

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

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

mp_moto = np.zeros((N , N))  # a to b への連結関係を記述

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

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

cnt = 0
for i in range(M) : 
    visited = np.zeros(N)
    mp = copy.deepcopy(mp_moto)
    #どれか一つの辺を取り除く
    s = s_list[i]
    mp[s[0] - 1 , s[1] - 1] = 0
    mp[s[1] - 1 , s[0] - 1] = 0
    df(0)
    if sum(visited) != N : cnt += 1

print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

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

    dfs(0)

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

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

print ans

Submission status: Accepted

Solution code:
#DEBUG = ""


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


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

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


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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

print(len(ans))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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


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

print(ans)

Submission status: Accepted

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

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

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

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

    print(ans)

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

main()

Submission status: Accepted

Solution code:
from collections import deque

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

visited = []

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

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


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

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

main()

Submission status: Accepted

Solution code:
import copy


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

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

    N: <=50
    M: <= 50

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

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

	print(ans)



solution()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]  # a[i],b[i]がi番目の辺を表す
    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
        # 頂点0からDFS
        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))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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]	
#print nl
#print a

def dfs(v,p):
	#print v
	F[v]=1
	for j in range(N+1):
		#頂点 v に隣接しているかつ未訪問
		if nl[v][j]!=0 and F[j]==0:
			#print v,j,nl[v][j]
			#DFS(次の頂点i, 次に親となる頂点v, d+ 頂点vと頂点iの間の辺のコスト)
			dfs(j,v)


#Connected graph
c_graph=[1]*(N+1)
c_graph[0]=0
#print "# c_graph"
#print c_graph

cnt=0
#print "# visit"
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
	#print nl
	dfs(1,-1)
	#print F
	if F!=c_graph:
		#print "Not connect"
		cnt+=1
	#Initalize neighbor list
	nl[x][y]=1
	nl[y][x]=1

print cnt

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

Submission status: Accepted

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