[python]伯準/BCDE/13023号/グラフ

質問する
ABCDE問題リンク
BOJアルゴリズムキャンプにはN人が参加している.人々は0番からN-1番で、友达がいる.
今日は以下のような友人関係のある人A,B,C,D,Eが存在するかどうかを検討してみましょう.

AとBは友達です.

BとCは友達です.

CとDは友達です.

DとEは友達です.

上記の友人関係があるかどうかを判断するプログラムを作成してください.
入力
第1行は、人の数N(5≦N≦2000)と友人関係の数M(1≦M≦2000)を与える.
2行目から、M行には整数aとbがあり、aとbが友達であることを示す.(0≦a,b≦N−1,a≠b)2回以上の友人関係はない.

5 5
0 1
1 2
2 3
3 0
1 4

しゅつりょく
問題条件に合致するA,B,C,D,Eがあれば、1がなくて出力0となる.

1

方法

では5人が1方向にナビゲートし、各頂点からDFSにナビゲートし、深さが5より大きいとすぐに1を出力します.そうしないと、すべてのナビゲーション後に

0を出力します.
コード#コード#

# url : https://www.acmicpc.net/problem/13023
# 난이도 : gold 5

import sys
sys.setrecursionlimit(10**6) # 백준 재귀제한 해제

n,m = map(int,sys.stdin.readline().split())

graph = [[] for _ in range(n)]

visited = [False]* n
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())

    graph[a].append(b)
    graph[b].append(a)


switch = False # 깊이가 5 이상일 때 켜지는 변수
def dfs(node,depth,visited):
    
    global switch
	
    # 깊이가 5 이상일 때 switch를 키고 리턴한다
    if depth >= 5:
        switch = True
        return
    

    
    for i in graph[node]:
        if visited[i] == False:
            visited[node] = True
            dfs(i,depth+1,visited)
            visited[node] = False

# 모든 정점에 대해 검색한다
for i in range(n):
    visited[i] = True
    dfs(i,1,visited)
    visited[i] = False
	
    # 스위치가 켜져있으면 1을 출력하고 멈춘다
    if switch == True :
        print(1)
        break

# 모든 정점을 검색해도 스위치가 켜져있지 않았다면 0을 출력한다
else:
    print(0)