import sys
n,m=map(int,sys.stdin.readline().split())
friend=[list() for i in range(n)]
for _ in range(m):
start,end=map(int,sys.stdin.readline().split())
friend[start].append(end)
friend[end].append(start)
def DFS_recur(first,idx):
visited[first]=1
if idx==4:
print(1)
exit()
for i in friend[first]:
if visited[i]==0:
DFS_recur(i,idx+1)
visited[i]=0
for i in range(n):
visited = [0 for i in range(n)]
DFS_recur(i,0)
print(0)
이 문제도 기본적인 그래프 문제 유형이라 생각한다.
A가 B를 알고 B가 C를 알고 C 가 D를 알고 D가 E를 아는 친구 관계가 있을떄
A-B-C-D-E 가 되는 관계가 있나 없나를 판단하는 문제이다.
나는 간단하게 DFS의 깊이가 4,5(시작이 1이면) 이 된다면 1를 출력하게 구현했다.
그리고 만약 0에서 시작했을때 모든 0에서 시작한 모든 방향들을 봐야하기에 그리고 그 방향이 실패했을 경우 다시 그 정점을 다른 정점에서 방문해야하기에 그 방향이 실패했을경우 돌아왔을땐 원래상태로 돌려줘야한다.
나는 이걸 백트래킹이라 생각한다.
뭐 하여튼 그래서 백트래킹으로 DFS 함수를 재귀적으로 돌림과 동시에 바로 밑에 다시 원래대로 돌려주는 코드를 한번더 작성했다.
Ez