백준 13023) ABCDE (python)

문제

풀이

 예시와 같은 ABCDE가 있다는 뜻은, 그래프 안의 특정 노드에서 5개 이상 연결되어있는 것이 있는지 묻는 것과 같다.

따라서 dfs를 통해서 그래프들을 탐험하게 하였고, 그중에 5개의 이상 노드가 연결되어 있을 때 (cnt>=4 일 때)

ans를 1로 만들어 1을 출력하게 하였다.

from collections import defaultdict
import sys
input = sys.stdin.readline
limit_number = 15000
sys.setrecursionlimit(limit_number)
dic = defaultdict(list)

n,m = map(int,input().split())

for i in range(m):
    a,b= map(int,input().split())
    dic[a].append(b)
    dic[b].append(a)

ans=0
def dfs(x,visited,cnt):
    global ans
    visited[x] = True
    if cnt >= 4:
        ans = 1
        return
    visited[x] = True
    for i in dic[x]:
        if not visited[i]:
            dfs(i,visited,cnt+1)
    visited[x] = False

for i in range(n):
    visited = [False for _ in range(n)]
    dfs(i,visited,0)
    if ans == 1:
        print(ans)
        break
    if i==n-1:
        print(0)