9466.プロジェクトを一時停止する

1287 ワード
Graph Cycle Graph Problem Solving テキストリンク

質問する

  • 時間制限: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


    基本的なループ問題です.
    [伯俊/c+]15654号:NとM(5)
    Python-デジタルリソース型