문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

# 13023
import sys
input = lambda: sys.stdin.readline().strip()

# DFS를 통해 친구라면 cnt += 1 해서 cnt == 5인지 확인한다

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append([])
    
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for g in graph:
    g.sort()
    
visited = [False] * n
    
def dfs(v, cnt = 1):
    global n, graph, visited
    visited[v] = True
    
    if cnt == 5:
        print("1")
        exit(0)
        
    for x in graph[v]:
        if visited[x]:
            continue
        dfs(x, cnt+1)
        
    visited[v] = False
    # 깊이 우선 탐색 시에 탐색을 실패한 경로에 대해서 삭제 반환하는 작업을 해주셔야 한다.
        
for i in range(n):
    visited = [False] * n
    dfs(i)
    
print("0")

백준 13023 ABCDE