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: Runtime Error

Solution code:
import collections
from typing import List, Tuple

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


def is_connected_graph(graph: List[List[int]]) -> bool:
    """グラフが連結か判定する。

    Args:
        - graph: 隣接リスト形式
    """
    graph_size = len(graph)
    if graph_size == 0:
        return True
    connected = [False] * graph_size
    dq = collections.deque([0])  # 暗黙的に0をrootとして探索する。
    connected[0] = True
    while dq:
        node = dq.popleft()
        for adjacent_node in graph[node]:
            if connected[adjacent_node]:
                continue
            connected[adjacent_node] = True
            dq.append(adjacent_node)
    return all(connected)


def enumerate_bridge(graph: List[List[int]]) -> List[Tuple[int, int]]:
    """グラフの橋を列挙する。

    Args:
        - graph: 隣接リスト形式

    Returns:
        - 橋の配列。ソートしていない。
    """
    graph_size = len(graph)
    if graph_size == 0:
        return True

    bridges = []

    visited = [False] * graph_size
    order = [-1] * graph_size
    lowlink = [float('inf')] * graph_size
    k = 0

    def __dfs(node, pre_node):
        nonlocal k
        visited[node] = True

        order[node] = k
        lowlink[node] = order[node]
        k += 1

        ct = 0

        for next_node in graph[node]:
            if not visited[next_node]:
                ct += 1
                __dfs(next_node, node)
                lowlink[node] = min(lowlink[node], lowlink[next_node])
                if order[node] < lowlink[next_node]:
                    bridges.append(
                        (min(node, next_node), max(node, next_node)))
            elif next_node != pre_node:
                lowlink[node] = min(lowlink[node], order[next_node])

    for i in range(graph_size):
        if not visited[i]:
            __dfs(i, -1)
    return bridges


print(len(enumerate_bridge(graph)))

Submission status: Runtime Error

Solution code:
#ABC075C

def dfs(v):
 visited[v]=True
 for v2 in xrange(n):
  if graph[v][v2]==False:
   continue
  if visited[v2]==True:
   continue
  dfs(v2)

n,m=map(int,raw_input().split())
graph=[[False for i in xrange(n)] for j in xrange(n)]
visited=[True for i in xrange(n)]
a=[0 for i in xrange(n)]
b=[0 for i in xrange(n)]

for i in xrange(m):
 a[i],b[i]=map(int,raw_input().split())
 a[i]-=1
 b[i]-=1
 graph[a[i]][b[i]]=graph[b[i]][a[i]]=True

res=0
for i in xrange(m):
 graph[a[i]][b[i]]=graph[b[i]][a[i]]=False
 for j in xrange(n):
  visited[j]=False
 dfs(0)
 bridge=False
 for j in xrange(n):
  if visited[j]==False:
   bridge=True
 if bridge:
  res+=1
 graph[a[i]][b[i]]=graph[b[i]][a[i]]=True

print res

Submission status: Runtime Error

Solution code:
#ABC075C

def dfs(v):
 visited[v]=True
 for v2 in xrange(n):
  if graph[v][v2]==False:
   continue
  if visited[v2]==True:
   continue
  dfs(v2)

n,m=map(int,raw_input().split())
graph=[[False for i in xrange(n)] for j in xrange(n)]
visited=[True for i in xrange(n)]
a=[True for i in xrange(n)]
b=[True for i in xrange(n)]

for i in xrange(m):
 a[i],b[i]=map(int,raw_input().split())
 a[i]-=1
 b[i]-=1
 graph[a[i]][b[i]]=graph[b[i]][a[i]]=True

res=0
for i in xrange(m):
 graph[a[i]][b[i]]=graph[b[i]][a[i]]=False
 for j in xrange(n):
  visited[j]=False
 dfs(0)
 bridge=False
 for j in xrange(n):
  if visited[j]==False:
   bridge=True
 if bridge:
  res+=1
 graph[a[i]][b[i]]=graph[b[i]][a[i]]=True

print res

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())		# 5 7

h=[]
for i in range(N+1):
	h.append([])

a=[]
b=[]

for i in range(M):
	A, B = map(int, input().split())		# 5 7
	h[A].append(B)
	h[B].append(A)
	a.append(A)
	b.append(B)



def dfs(Graph, Start, Visited=None):
	if(Visited==None): Visited = []
	Visited.append(Start)
	#print(Start, Visited)
	for Next in Graph[Start]:
		if( Next in Visited ): 
			#print("   Visited", Next, Visited)
			continue
		dfs(Graph, Next, Visited)

z=[_ for _ in range(1, N+1)]
#print(z)
ans=0

import copy
for i in range(N):
	g = copy.deepcopy(h)
	
	A = a[i]
	B = b[i]
	n = i+1

	g[A].remove(B)
	g[B].remove(A)
	
	Visited = []
	dfs(g, n, Visited)
	
	#print(Visited)
	if len( list(set(z) - set(Visited)) ) > 0:
	    ans += 1

	
print(ans)

Submission status: Runtime Error

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

g=[[False for i in range(N)] for j in range(N)]
ab=[()]*N
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: Runtime Error

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

g=[[False for i in range(N)] for j in range(N)]
ab=[()]*N
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]=1
    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: Runtime Error

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(N):
    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: Runtime Error

Solution code:
from itertools import permutations

def solve():
    n, k = map(int, input().split())
    xs, ys = [], [] 
    for _ in range(n):
        x, y = map(int, input().split())
        xs.append(x)
        ys.append(y)
    ans = ((10 ** 9) * (10 ** 9)) ** 2
    for x1 in xs:
        for x2 in xs:
            for y1 in ys:
                for y2 in ys:
                    minX, maxX = sorted([x1, x2])
                    minY, maxY = sorted([y1, y2])
                    cnt = 0
                    for i in range(n):
                        if minX <= xs[i] <= maxX and minY <= ys[i] <= maxY:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (maxX - minX) * (maxY - minY))
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Runtime Error

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

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: Runtime Error

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


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)