[伯俊/python 3]13023 ABCDE


https://www.acmicpc.net/problem/13023

に答える


一部の人は友達の時、A-B-C-D-Eのような友達関係があるかどうか.DFSで解決できます.

コード#コード#

import sys
input = sys.stdin.readline

# DFS
def dfs(target, num):
    if num == 4:
        print(1)
        exit()

    for node in graph[target]:
        if not visited[node]:
            visited[node] = True
            dfs(node, num + 1)
            visited[node] = False


# Initial
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    # Undirected Graph
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


visited = [False for _ in range(N)]

for node in range(N):
    visited[node] = True
    dfs(node, 0)
    visited[node] = False

print(0)