白駿-13023号ABCDE

質問リンク

😊 問題の概要

a-b-c-d-eのように、全部で5つの接続があることを確認します!接続されている場合は1を出力し、接続されていない場合は0を出力します.

😂 key point!!

深さ優先探索または幅優先探索は、ノードの深さ(深さ)を求めることができる必要があります.
筆者はdfsを用いてcount変数によりノードの深さを理解する.

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

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

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

# 깊이를 나타내는 count == 4인 것을 나타내기 위한 전역 변수
check = [0] 

def dfs(graph,v,visited,count):
    
    visited[v] = True
    
    if count == 4:
        check[0] = 1 
        return 
    
    for i in graph[v]:
        if visited[i] == False:
            dfs(graph,i,visited,count+1)
            visited[i] = False        #노드의 다른 길 방문을 위해 리셋

result = 0

visited = [False] * n

for i in range(n):
    visited[i] = [False]              #방문기록을 나타내는 visited 리셋
    dfs(graph,i,visited,0)
    if check[0] == 1:
        result = 1
        break

if result == 1:
    print(1)
else:
    print(0)