質問する

時間制限:3秒

メモリ制限:256 MB

Problem Analysis

リーグ戦を含めるとチームですが、リーグ戦を入れなければチームではありません.ループを探すことが問題の核心です.スタック上のノードにDepth First Searchでアクセスし、Cycleを検索します.

Algorithm

アクセスの色

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

基本的なループ問題です.