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)