Submission #1793754

---

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(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(start, path,loops)
            path.pop()

#入力
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(i,[i],loops)
#ループに属する辺(橋でない辺)の検索
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])
#答えは全体の辺の数からループでないものを引いた数
print(M-len(not_bridge))

Submission Info

Judge Result