문제

• 
• 시간 제한: 3초
• 메모리 제한: 256MB

Problem Analysis

싸이클에 포함되면 같은 팀이고, 싸이클에 포함되지 못하면 팀이 아니다. 싸이클을 찾는 것이 문제의 핵심이다. Depth First Search를 통해 stack에 올려져 있는 node에 방문하는지 확인하면서 Cycle을 찾으면 된다.

Algorithm

visited의 color를

WHITE: 방문하지 않음
GRAY: 조사 중, stack에 올려짐
BLACK: 조사 완료

로 두고 아래의 알고리즘을 진행한다.

1. 방문하지 않은 학생을 시발점으로 DFS를 시작한다.
2. 방문 중인 Node를 GRAY로 두고 인접 nodes를 조사한다.
  - 인접 node가 BLACK이라면, 이미 팀에 속하거나 그렇지 못한 것이므로, 현재 node는 팀에 속하지 못한다.
  - 인접 node가 WHITE라면, recursive call을 한다. return 값이 cycle의 최상단 조상이라면 해당 위치까지만 팀에 count 한다.
  - 인접 node가 GRAY라면, 해당 node는 cycle에 속하는 최상위 조상이다. 해당 node를 return 한다.
  - 해당 node의 조사가 끝나면, BLACK으로 둔다. 위 상황에 맞게, 최상위 cycle의 번호 또는 null을 return.
3. 끝날 때까지, 1부터 다시 시작한다.

Data Structure

• 학생의 선택을 저장할 Array
• visited array, color{ white, gray, black}

결과

Other

기본적인 Cycle 찾기 문제이다.