Submission #1793776

---

Source Code Expand

import copy

def set(adjacent,edge):
    for x in edge:
        adjacent[x[0]].append(x[1])
        adjacent[x[1]].append(x[0])

    
def search(goal,path):
    n = path[len(path) - 1]
    if n == goal:
        print(path)
    else:
        for x in adjacent[n]:
            if x not in path:
                path.append(x)
                search(goal, path)
                path.pop()

def search_loop_node(adjacent,start,path,node_loops):
    n = path[len(path)-1]
    for x in adjacent[n]:
        if x == start and len(path) >=2 and path[-2] != start :
            path.append(x)
            node_loops.append(copy.deepcopy(path))
            path.pop()
        elif x not in path:
            path.append(x)
            search_loop_node(adjacent,start, path,node_loops)
            path.pop()

def main():
    #入力
    N, M = [int(i) for i in input().split()]
    edge = []
    for i in range(M):
        a,b = [int(i) for i in input().split()]
        edge.append([a,b])

    #辺の生成
    adjacent=[ [] for i in range(N+1)]
    loops=[]
    set(adjacent,edge)
    #ループの検索
    for i in range(N):
        search_loop_node(adjacent,i,[i],loops)
    #ループに属する辺(橋でない辺)の検索
    not_bridge = []
    for loop in loops:
        pre_node = loop[0]
        for node in loop:
            if pre_node < node and [pre_node, node] not in not_bridge:
                not_bridge.append([pre_node,node])
            pre_node = node
    #答えは全体の辺の数からループでないものを引いた数
    print(M-len(not_bridge))
    
if __name__ == '__main__':
    main()

Submission Info

Judge Result