위상정렬에서 BFS로 사이클 검사하는 방법

사이클이 생겼다는 것은 모든 정점을 방문하지 못하게 된다. 따라서 정점의 갯수만큼 큐를 돌리면서 중간에 큐가 비었다는 것은 사이클이 생겼다는 것을 의미한다

 

그리고 예외상황으로 첫번째와 마지막에서 사이클이 발생하는 것을 막기 위해서는 마지막에 한 번 더 indegree 검사를 해야만 사이클을 철저히 막을 수 있다

 

for(int i=0; i<정점갯수; i++) {
    if(q.empty()) {
      // 사이클 존재
      break; 
    }
}

for(int i=0; i<정점갯수; i++) {
    if(indegree[i] > 0) {
      // 사이클 존재
      break;
    }
}