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:
import sys
from copy import deepcopy
# coding: utf-8


class Node(object):

    def __init__(self, value):
        self.value = value
        self.visited = False
        self.adjacencies = []

    def __repr__(self):
        return self.__str__()

    def __str__(self):
        return str(self.value)

    def add_adjaency(self, node):
        if isinstance(node, Node):
            self.adjacencies.append(node)
        else:
            raise TypeError('Type "Node" expected, but received {0}'.format(type(node)))

    def remove_adjacency(self, node):
        self.adjacencies.remove(node)

    def is_visited(self):
        return self.visited

    def mark_as_visited(self):
        self.visited = True

    def clear_history(self):
        self.visited = False


class Graph(object):

    def __init__(self):
        self.nodes = []
        self.root = None
        self.search_result = None  # Not Thread Safe Now.

    def __str__(self):
        return self.nodes

    def mark_as_root(self, node):
        self.root = node

    def add_node(self, node):
        if isinstance(node, Node):
            self.nodes.append(node)
            if self.root is None:
                self.mark_as_root(node)
        else:
            raise TypeError('Type "Node" expected, but received {0}'.format(type(node)))

    @staticmethod
    def add_uni_link(from_node, to_node):  # unidirectional
        from_node.add_adjaency(to_node)

    @staticmethod
    def remove_uni_link(from_node, to_node):  # unidirectional
        from_node.remove_adjacency(to_node)

    @staticmethod
    def add_bi_link(node1, node2):  # bidirectional
        node1.add_adjaency(node2)
        node2.add_adjaency(node1)

    @staticmethod
    def remove_bi_link(node1, node2):  # bidirectional
        node1.remove_adjacency(node2)
        node2.remove_adjacency(node1)

    def clear_history(self):
        for node in self.nodes:
            node.clear_history()

    def dfs(self, value, start_node=None):
        """Depth First Search
        :returns reference of node where the value matches attribute value.
        """
        self.search_result = None
        self.clear_history()

        if start_node is None:
            start_node = self.root

        self._dfs(start_node, value)

    def _dfs(self, start_node, value):
        self._visit(node=start_node, search_value=value)

        for adjacency in start_node.adjacencies:
            if not adjacency.is_visited():
                self._dfs(start_node=adjacency, value=value)
        return

    def _visit(self, node, search_value):
        node.mark_as_visited()
        if node.value == search_value:
            self.search_result = node
        else:
            return


def main():

    # Get Args
    a, b, N, M = _input_args()  # get arguments as an array from console/script parameters.

    # Call main Logic
    result = _main(a, b, N, M)

    # Output a result in a correct way.
    _output_result(result)


def _main(a, b, N, M):
    """Write Main Logic here for the contest.

    :param args: arguments
    :type args: list
    :return: result
    :rtype: depends on your logic.
    """

    bridges = 0  # counter
    offset = -1  # between subject

    for i in range(M):
        # Initialize Graph
        graph = Graph()

        # Add nodes
        for n in range(N):
            graph.add_node(Node(value=n + 1))

        # Add lines, but drops one of them
        a_temp = deepcopy(a)
        b_temp = deepcopy(b)

        del a_temp[i]
        del b_temp[i]

        # Add lines
        for n1_index, n2_index in zip(a_temp, b_temp):
            graph.add_bi_link(graph.nodes[n1_index + offset], graph.nodes[n2_index + offset])

        # check if all node can be found by dfs
        for nd in range(N):
            graph.dfs(value=nd+1)
            if graph.search_result is None:
                bridges += 1
                break

    return bridges


def _input_args():

    arguments = _get_args_from_multiple_lines(end_of_lines_char=[''], limit=10000000)

    a = []
    b = []
    N, M = map(int, arguments[0].split())
    pairs = arguments[1:]

    for i in range(0, len(pairs)):
        ai, bi = map(int, pairs[i].split())
        a.append(ai)
        b.append(bi)

    return a, b, N, M


def _input():
    # If Subject requires interactive input, use this and patch mock in unittest.
    return input()  # Change if necessary.


def _get_args_from_multiple_lines(end_of_lines_char=[''], limit=10000000):
    """Get arguments from multiple lines standard input.

    :param end_of_lines_char: Strings that indicate the end of lines.
    :type end_of_lines_char: list of str
    :param limit: If a number of the input line are certain, you can use this param to close prompt immediately.
    :type limit: int
    :return: args
    :rtype list of str
    """
    args = []
    for i in range(limit):
        try:
            arg = _input()
            if arg in end_of_lines_char:
                break
            args.append(arg)
        except EOFError:  # Supports EOF Style. (Very Rare case)
            break
    return args


def _output_result(result):
    print('{}'.format(str(result)))  # Same as above, but more versatile.


if __name__ == '__main__':
    main()

Submission status: Accepted

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

E = [[] for i in range(N)]

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

visited = []


def search(pos):
    for n_pos in E[pos]:
        if n_pos not in visited:
            visited.append(n_pos)
            search(n_pos)

count = 0
for i in range(M):
    visited = []
    E = [[] for i in range(N)]
    for j in range(M):
        if j == i:
            continue
        E[ab[j][0]].append(ab[j][1])
        E[ab[j][1]].append(ab[j][0])
    search(0)
    if len(visited) < N:
        count += 1

print(count)

Submission status: Accepted

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):  # (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):  # (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: Accepted

Solution code:
def BFS(n,path):
  """頂点数nと隣接リストpathを与え、連結かどうかをチェックする"""
  check=[0]*n
  check[0]=1
  Que=[0]
  while Que:
    u=Que.pop(-1)
    for v in path[u]:
      if check[v]==0:
        check[v]=1
        Que.append(v)
  if check!=[1]*n: return 1
  else: return 0

N,M=map(int,input().split())
A=[]
B=[]
for i in range(M):
  a,b=map(int,input().split())
  A+=[a-1]
  B+=[b-1]
ans=0
for i in range(M):
  edges=[[] for i in range(N)]
  for j in range(M):
    if j!=i:
      edges[A[j]]+=[B[j]]
      edges[B[j]]+=[A[j]]
  ans+=BFS(N,edges)
print(ans)

Submission status: Accepted

Solution code:

N,M = [int(i) for i in input().split()]
Nodes = []
Mlist = []
count = 0
for i in range(N):
    Mlist.append(1)
for i in range(M):
    Nodes.append(list(map(int, input().split())))


def search(x):
    Mlist2[x-1] = 0
    for i in range(len(Nodes2)):
        if x in Nodes2[i]:
            if Nodes2[i].index(x) == 0:
                if Mlist2[Nodes2[i][1]-1] != 0:
                    search(Nodes2[i][1])
                else: continue
            if Nodes2[i].index(x) == 1:
                if Mlist2[Nodes2[i][0]-1] != 0:
                    search(Nodes2[i][0])
                else: continue
        else: continue
    #print(Mlist2)
    return(Mlist2)

def cout(x):
    answer = 1
    for i in range(len(x)):
        if x[i] == 0:
            continue
        else:
            answer = 0
            break
    if answer == 1:
        return 1
    if answer == 0:
        return 0

for i in range(M):
    #print (i)
    Nodes2 = Nodes[:]
    Mlist2 = Mlist[:]
    del Nodes2[i]
    ans = cout(search(1))
    if ans == 0:
        count += 1
print(count)

Submission status: Accepted

Solution code:

N,M = [int(i) for i in input().split()]
Nodes = []
Mlist = []
count = 0
for i in range(N):
    Mlist.append(1)
for i in range(M):
    Nodes.append(list(map(int, input().split())))


def search(x):
    Mlist2[x-1] = 0
    answer = 1
    for i in range(len(Nodes2)):
        if x in Nodes2[i]:
            if Nodes2[i].index(x) == 0:
                if Mlist2[Nodes2[i][1]-1] != 0:
                    search(Nodes2[i][1])
                else: continue
            if Nodes2[i].index(x) == 1:
                if Mlist2[Nodes2[i][0]-1] != 0:
                    search(Nodes2[i][0])
                else: continue
        else: continue
    #print(Mlist2)
    for i in range(len(Mlist2)):
        if Mlist2[i] == 0:
            continue
        else:
            answer = 0
            break
    if answer == 1:
        return 1
    if answer == 0:
        return 0

for i in range(M):
    #print (i)
    Nodes2 = Nodes[:]
    Mlist2 = Mlist[:]
    del Nodes2[i]
    ans = search(1)
    if ans == 0:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m = map(int, raw_input().split(" "))
bridges = [[]]
check = [0]
needline = 0
for i in range(n):
    bridges.append([])
for t in range(m):
    x,y = map(int, raw_input().split(" "))
    bridges[x].append(y)
    bridges[y].append(x)
#    brid.append()

#print bridges

def recursivebridge(k,count,goal,checki):
    boo = False
#    print k
    for h in bridges[k]:
        if count >= 2 and h == goal:
            boo = True
        elif h not in checki:
            checky = checki[:]
            checky.append(h)
            boo = boo or recursivebridge(h,count+1,goal,checky)
    return(boo)

for i in range(n+1):
    if i in check:
        continue
    checkcopy = check[:]
    checkcopy.append(i)
    if recursivebridge(i,0,i,checkcopy) is False:
#        print "false"
        needline += 1


if needline > m:
    needline = m
print needline

Submission status: Accepted

Solution code:
#!/usr/bin/python

# AtCoder Beginner Contest 075
# C - Bridge

from sys import stdin

def nReachable(node, edges):
  visited = []
  gray    = [node]
  while len(gray) > 0:
    n    = gray[0]
    gray = gray[1:]
    if n not in visited:
      visited.append(n)
      gray.extend([e[1] for e in edges if e[0] == n])
      gray.extend([e[0] for e in edges if e[1] == n])
  return len(visited)

def solve(N, E):
  cnt = 0
  for i in range(len(E)):
    EE = E[:i] + E[i + 1:]  # drop E[i]
    if nReachable(1, EE) < N:
      cnt += 1
  return cnt

def splitIntoInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, M = splitIntoInt(stdin.readline())
E = []
for i in range(M):
  a, b = splitIntoInt(stdin.readline())
  E.append((a, b))
print(solve(N, E))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
INF = 10**100
r = range

class infix(object):
    def __init__(self, function):
        self.function = function

    def __ror__(self, other):
        self.left = other
        return self

    def __or__(self, other):
        return self.function(self.left, other)

    def __call__(self, value1, value2):
        return self.function(value1, value2)

@infix
def c(f_t_u, f_u_r): return lambda t: f_u_r(f_t_u(t))

class _Ap(object):
    def __rlshift__(self, other):
        self.value = other
        return self

    def __rshift__(self, other):
        return other(self.value)
Ap = _Ap()
A = Ap

#d = {1:2, 3:5, 6:10, 1000043:3814}
#zip(d.keys(), d.values())<<ap>>(list |c| sorted |c| reversed |c| list |c| print)

n, m = map(int, input().split())
g = [set() for i in range(n+1)]
e = set();
for i in range(m):
    a,b=map(int,input().split())
    b<<A>>g[a].add
    a<<A>>g[b].add
    (a,b)<<A>>e.add

color = [0]*(n+1)
def dfs(u, p):
#    print(u, p);
    color[u] = 1
    for next_u in g[u]:
        if next_u == p:
            continue
        if not color[next_u]:
            dfs(next_u, u)

ret = 0
for edge in e:
    color = [0]*(n+1)
    g[edge[0]].remove(edge[1]);
    g[edge[1]].remove(edge[0]);
#    print(g)
    dfs(edge[0], -1)
    ret += color[edge[1]]
    g[edge[0]].add(edge[1]);
    g[edge[1]].add(edge[0]);

print(m-ret);

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
INF = 10**100
r = range

class infix(object):
    def __init__(self, function):
        self.function = function

    def __ror__(self, other):
        self.left = other
        return self

    def __or__(self, other):
        return self.function(self.left, other)

    def __call__(self, value1, value2):
        return self.function(value1, value2)

@infix
def c(f_t_u, f_u_r): return lambda t: f_u_r(f_t_u(t))

class _Ap(object):
    def __rlshift__(self, other):
        self.value = other
        return self

    def __rshift__(self, other):
        return other(self.value)
Ap = _Ap()
A = Ap

#d = {1:2, 3:5, 6:10, 1000043:3814}
#zip(d.keys(), d.values())<<ap>>(list |c| sorted |c| reversed |c| list |c| print)

n, m = map(int, input().split())
g = [set() for i in range(n+1)]
e = set();
for i in range(m):
    a,b=map(int,input().split())
    g[a].add(b);
    g[b].add(a);
    e.add((a,b))

color = [0]*(n+1)
def dfs(u, p):
#    print(u, p);
    color[u] = 1
    for next_u in g[u]:
        if next_u == p:
            continue
        if not color[next_u]:
            dfs(next_u, u)

ret = 0
for edge in e:
    color = [0]*(n+1)
    g[edge[0]].remove(edge[1]);
    g[edge[1]].remove(edge[0]);
#    print(g)
    dfs(edge[0], -1)
    ret += color[edge[1]]
    g[edge[0]].add(edge[1]);
    g[edge[1]].add(edge[0]);

print(m-ret);

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
pp=[[0 for i in range(2)] for j in range(m)]
not_bridge=0

#深さ優先探索-------------------------------------------------------------
#参照元：Python3でグラフの実装＆深さ優先探索・幅優先探索の実装
#http://muromura.hatenablog.com/entry/2017/07/16/025414
def dfs(Graph, Start, Vn, Visited=None):
  
##追加（空から読んでも動くように修正）-----------------------
  if Graph[Start]==[] and Visited==None: 
        Next=Start+1        
        dfs(Graph, Next, Vn, Visited)  #再帰
  else:
##--------------------------------------------------------

    if (Visited==None):  Visited = [] #開始点のときに探索済みリストをつくる
    Visited.append(Start)  #現在の頂点を探索済みリストに加える
#    print(Start, "\n", Visited)  #現在の頂点と探索済みリストを表示
    if len(Visited)==Vn: #全点訪問済みの場合、橋ではない
        global not_bridge
        not_bridge=not_bridge+1
    for Next in Graph[Start]:  #次に探索する頂点の候補
        if ( Next in Visited ):  continue  #訪問済みリストにある頂点は飛ばす
        dfs(Graph, Next, Vn, Visited)  #再帰
#-----------------------------------------------------------------------        

for i in range(m) :
    pp[i] =[int(i) for i in input().split()]

for i in range(m) : #辺を１つ削除してその辺が橋かどうかを深さ優先探索で調べる
    p=pp[:]
    del p[i]

#隣接リスト
    l = [[] for i in range(n+1)] #頂点の数+1
    for pi in p:  #0-originedに注意、l[0]は空
        l[pi[0]].append(pi[1])
        l[pi[1]].append(pi[0])

    
    #頂点０（１）から探索
    dfs(l, 0, n)
    
print(m-not_bridge)

Submission status: Accepted

Solution code:
def dfs(num):
    global used, G
    used.add(num)
    for t in G[num]:
        if t not in used:
            dfs(t)

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

ans = 0
for a, b in es:
    G[a].remove(b)
    G[b].remove(a)
    used = set()
    dfs(0)
    if len(used) != N:
        ans += 1
    G[a].append(b)
    G[b].append(a)

print(ans)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
pp=[[0 for i in range(2)] for j in range(m)]
ans=0

#深さ優先探索---------------------------------
#参照元：Python3でグラフの実装＆深さ優先探索・幅優先探索の実装
#http://muromura.hatenablog.com/entry/2017/07/16/025414
def dfs(Graph, Start, Vn, Visited=None):
  
##追加（空から読んでも動くように修正）-----------------------
  if Graph[Start]==[] and Visited==None: 
        Next=Start+1        
        dfs(Graph, Next, Vn, Visited)  #再帰
  else:
##--------------------------------------------------------
    if (Visited==None):  Visited = [] #開始点のときに探索済みリストをつくる
    Visited.append(Start)  #現在の頂点を探索済みリストに加える
#    print(Start, "\n", Visited)  #現在の頂点と探索済みリストを表示
#    print(len(Visited))
    if len(Visited)==Vn:
        global ans
        ans=ans+1
    for Next in Graph[Start]:  #次に探索する頂点の候補
        if ( Next in Visited ):  continue  #訪問済みリストにある頂点は飛ばす
        dfs(Graph, Next, Vn, Visited)  #再帰
#--------------------------------------------------------        

for i in range(m) :
    pp[i] =[int(i) for i in input().split()]

for i in range(m) : #辺を１つ削除してその辺が橋かどうかを深さ優先探索で調べる
    p=pp[:]
    del p[i]

#隣接リスト
    l = [[] for i in range(n+1)] #頂点の数+1
    for pi in p:  #0-originedに注意
        l[pi[0]].append(pi[1])
        l[pi[1]].append(pi[0])
#    print(l)
    
    #頂点０（１）から探索
    dfs(l, 0, n)
#    print(ans)
print(m-ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import copy

def bfs(n, ls, mat):
    tmat = copy.deepcopy(mat)
    cnt = 0
    for a, b in ls:
        tmat[a][b] = tmat[b][a] = 0
        visited = [0 for i in range(n+2)]
        que = [a]
        
        while que:
            st = que.pop(0)
            visited[st] = 1
            for i in range(1, n + 1):
                if tmat[st][i] == 1 and visited[i] != 1:
                    que.append(i)
                    
        tmat = copy.deepcopy(mat)
        if sum(visited) != n:
            cnt += 1
    return cnt

n, m = list(map(int, input().split()))
ls = []
for i in range(m):
    a, b = list(map(int, input().split()))
    ls.append((a, b))
    
mat = [[0 for i in range(m + 2)] for j in range(m + 2)]
for a, b in ls:
    mat[a][b] = mat[b][a] = 1
    
cnt = bfs(n, ls, mat)
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def dfs(s):
    global used, G
    used.add(s)
    for t in G[s]:
        if t not in used:
            dfs(t)

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

ans = 0
for a, b in es:
    G[a].remove(b)
    G[b].remove(a)
    used = set()
    dfs(0)
    if len(used) != N:
        ans += 1
    G[a].append(b)
    G[b].append(a)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
import sys
sys.setrecursionlimit(10**7)

def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0] * N]
    for _ in [0] * M:
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    bridges = len(get_lowlink(edges, M)[0])
    print(bridges)
 
"""
edge_numはedgeの数
"""
def get_lowlink(edges, edge_num):

 
    n = len(edges)
    order = [-1] * n
    low = [float("inf")] * n
    bridges = []
    articulations = [0] if edge_num == n-1 and len(edges[0]) > 1 else []
    append_bridge, append_articulation = bridges.append, articulations.append
 
    def dfs(v, prev, k):
        order[v] = low[v] = k
 
        is_articulation = False
        for dest in edges[v]:
            if order[dest] == -1:
                dfs(dest, v, k + 1)
                if low[v] > low[dest]:
                    low[v] = low[dest]
                if order[v] < low[dest]:
                    append_bridge((v, dest))
                is_articulation |= order[v] <= low[dest]
 
            elif dest != prev and low[v] > order[dest]:
                low[v] = order[dest]
 
        if v > 0 and is_articulation:
            append_articulation(v)
 
    dfs(0, 0, 0)
    return bridges, articulations
 
 
if __name__ == "__main__":
    solve()

Submission status: Accepted

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


def dfs(index, connects):
    global IS_VISITED

    # print(index)
    # print(IS_VISITED)
    # print(connects)

    if index in connects.keys():
        IS_VISITED[index] = True
        nodes = [x for x in connects[index]]
    else:
        return

    for node in nodes:
        if IS_VISITED[node] == False:
            dfs(node, connects)


def is_connected(inputs):
    global IS_VISITED

    connects = {}
    for edge in inputs:
        edge = [int(edge[0]), int(edge[1])]
        if edge[0] in connects.keys():
            connects[edge[0]].append(edge[1])
        else:
            connects[edge[0]] = [edge[1]]

        if edge[1] in connects.keys():
            connects[edge[1]].append(edge[0])
        else:
            connects[edge[1]] = [edge[0]]

    # print(connects)
    IS_VISITED = [True] + [False for x in range(int(N))]
    dfs(1, connects)
    return len(IS_VISITED) is not len([1 for idx in range(len(IS_VISITED)) if IS_VISITED[idx]])


N, _ = input().split(" ")
#IS_VISITED = [False for x in range(int(N))]
IS_VISITED = []

inputs = []
while True:
    try:
        inputs.append(input().split(" "))
    except EOFError:
        break


count = 0
for i in range(len(inputs)):
    # ひとつずつ辺を落として、まだつながっているか調べる
    if is_connected(inputs[:i] + inputs[i + 1:]):
        # print(i, inputs[i])
        count += 1

print(count)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
e=[[0 for i in range(n)] for j in range(n)]
xx=[]
for i in range(m):
 x=i2()
 x[0]-=1
 x[1]-=1
 xx.append(x)
 e[x[0]][x[1]]=1
 e[x[1]][x[0]]=1
d=[0 for i in range(n)]
def dfs(v):
    d[v]=1
    for i in range(n):
        if e[v][i]==1 and d[i]==0:
            dfs(i)
a=0
for i in xx:
 e[i[0]][i[1]]=0
 e[i[1]][i[0]]=0
 dfs(0)
 if 0 in d:
   a+=1
 d=[0 for j in range(n)]
 e[i[0]][i[1]]=1
 e[i[1]][i[0]]=1
print(a)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a=[0]*M
b=[0]*M
adj = [[0 for _ in range(N)] for _ in range(N)]
flag = [0]*N
bridge = 0

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

def dfs(cv):
    flag[cv-1]=1
    for i,x in enumerate(adj[cv-1]):
        if x==1 and flag[i]==0 :
            dfs(i+1)
    return

for i in range(M):
    flag=[0]*N
    adj[a[i]-1][b[i]-1] = adj[b[i]-1][a[i]-1] = 0
    dfs(1)
    if sum(flag)<N:
        bridge+=1
    adj[a[i]-1][b[i]-1] = adj[b[i]-1][a[i]-1] = 1

print(bridge)

Submission status: Accepted

Solution code:
def dfs(p, reached):
    global N, G
    reached.append(p)
    for i in range(N):
        if G[p][i] and i not in reached:
            reached = dfs(i, reached[:])
    return reached

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

ans = 0
for i in range(N):
    for j in range(i):
        if G[i][j]:
            G[i][j] = False
            G[j][i] = False
            if len(dfs(0, [])) < N:
                ans += 1
            G[i][j] = True
            G[j][i] = True

print(ans)

Submission status: Accepted

Solution code:
import sys

numBridge = 0
visited = set()

def singletonSet(x):
    r = set()
    r.add(x)
    return r

def dfs(start, stack):
#    print("dfs: stack = {}".format(stack))
    global numBridge
#    print("added {} to visited".format(start))
    visited.add(start)
    tree[start] = []
    for v in nbr[start]:
#        print("checking {}->{}".format(start, v))
        if v in done[start]:
            pass
        else:
            done[v].add(start)
            tree[start].append(v)
            if v in visited:
#                print("visited {}->{}".format(start, v))
                loop[start].add(v)
                while not v in stack:
                    w = revtree[v]
                    loop[w].add(v)
                    v = w
                t = v
#                print("common top is {}".format(t))
                v = start
                while v != t:
                    w = revtree[v]
                    loop[w].add(v)
                    v = w
            else:
                revtree[v] = start
                dfs(v, stack.union(singletonSet(start)))

def count():
    c = 0
    for p in range(1, n + 1):
#        print("tree[{}] = {}".format(p, tree[p]))
#        print("loop[{}] = {}".format(p, loop[p]))
        c += len(tree[p]) - len(loop[p])
    return c

f = sys.stdin
n, m = map(int, next(f).rstrip().split(' '))
nbr     = [[]    for _ in range(n + 1)]
tree    = [[]    for _ in range(n + 1)]
done    = [set() for _ in range(n + 1)]
revtree = [None  for _ in range(n + 1)]
loop    = [set() for _ in range(n + 1)]
for line in f:
    (p, q) = map(int, line.rstrip().split(' '))
#    print("p, q = {}, {}".format(p, q))
    nbr[p].append(q)
    nbr[q].append(p)

dfs(1, set())
print(count())

Submission status: Accepted

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

visited = []

def dfs(adjacent_matrix, current_node, num_nodes):
    for next_node in range(num_nodes):
        if adjacent_matrix[current_node][next_node] == False:
            continue
        if visited[next_node] == True:
            continue
        visited[next_node] = True
        dfs(adjacent_matrix, next_node, num_nodes)

def main():
    num_nodes, num_edges = map(int, input().split(" "))
    
    edges = []
    for _ in range(num_edges):
        start_node, end_node = map(int, input().split(" "))
        edges.append([start_node - 1, end_node - 1])

    adjacent_matrix = [[False for _ in range(num_nodes)] for _ in range(num_nodes)]
    for e in edges:
        adjacent_matrix[e[0]][e[1]] = adjacent_matrix[e[1]][e[0]] = True

    num_bridges = 0
    global visited
    visited = [False] * num_nodes
    for e in edges:
        adjacent_matrix[e[0]][e[1]] = adjacent_matrix[e[1]][e[0]] = False

        dfs(adjacent_matrix, 0, num_nodes)
        
        is_connected = True
        for v in visited:
            if v == False:
                is_connected = False
        
        for i in range(num_nodes):
            visited[i] = False

        if is_connected == False:
            num_bridges += 1

        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:
def dfs(x):
    visited[x] = True
    for x2 in xrange(n):
        if graph[x][x2] == False: continue
        if visited[x2] == True: continue
        dfs(x2)

def main():
    global n, m, graph, visited

    n, m = map(int, raw_input().split())
    graph = [[False for _ in xrange(n)] for _ in xrange(n)]
    ai = []
    bi = []
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ai.append(a)
        bi.append(b)
        graph[a][b] = graph[b][a] = True
    ans = 0

    for i in xrange(m):
        graph[ai[i]][bi[i]] = graph[bi[i]][ai[i]] = False
        visited = [False for _ in xrange(n)]
        bridge = True

        dfs(0)
        if all(visited): bridge = False
        if bridge: ans += 1
        graph[ai[i]][bi[i]] = graph[bi[i]][ai[i]] = True

    print ans
    return 0

if __name__ == '__main__':
    main()

Submission status: Accepted

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(M):
	g = copy.deepcopy(h)
	
	A = a[i]
	B = b[i]

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

	
print(ans)