[GeeksForGeeks] Detect Cycle in a directed graph

🔒 문제

그림을 누르면 해당 문제 링크로 이동한다.

💭 생각의 흐름

문제를 푸는 입장에서 유형을 보지 않을 수가 없는데

조건: 'directed graph' + can connect itself

∴ Union-Find 알고리즘을 사용하기 어렵다.

 

총 2가지 방식으로 풀이할 수 있겠다.

1.  Topological Sort using BFS (Kahn's Algorithm) 풀이

2.  DFS 변형 풀이

여기선 2번 방법을 선택해서 풀이해보겠다.

 

DFS 변형 풀이법의 핵심은 다음과 같다.

전형적인 DFS 코드를 쓰되, 부모 노드 Set(지나온 부모 노드 방문여부)을 Keep 한다!

DFS 를 재귀적으로 호출하면서 이전 스택으로 되돌아 가기 직전에 방문처리 되지 않은 상태로 되돌리기 위해 (부모 노드 Set 업데이트) 부모 노드 방문을 취소한다.

bool dfsDetectCycle(int V, std::vector<int> *adj) {
  visited[V] = true;
  ancestorVisited[V] = true;

  //..... (중략)
  
  // before return to parent node, redo ancestor Visited array
  ancestorVisited[V] = false;
}

 

🔑 풀이