BOJ-9466基準項目

11948 ワード
Problem Solving algorithm テキストリンク

質問する

  • 質問リンク
  • 試験数Tは
    • を与える.
  • 学生数Nが与えられる.
  • 人の学生からなるグループstd.
  • チームを構成できない学生の数を探す問題だ.

    • に答える

  • 題の並びは有向図で表すことができる.
    • 上の有向図では,Cycleがあれば,Cycleを構成するノードは問題でいうチームを形成する.したがって,ループを構成しないすべてのノードを出力すればよい.
    Cycleを構成しないノードを出力する方法を定義します.
  • は、キューに枠線のないノード(零度ノード)を提供する.
    • ポーリング
  • キュー.
  • の次のノードの度数が現在のノードに接続されている場合を除き、0の場合、キューに提供されます.
    • すなわち、零度ノードは、無条件ループを形成しないノードである.また,このノードに沿って歩くと,接続されたedge以外の度数は0であり,(indegree - 1)となりループがないことを示すため,キューに入れて探索を継続する.
    上記の手順を繰り返して、cycleが存在しないすべてのノードを参照します.これは、問題にチームを構成していない人を探索し、これらのノードの数を数え、答えを出力することができることを意味します.

    コード#コード#

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while (T -- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] std = new int[N + 1];
            int[] indegree = new int[N + 1];

            String[] selectList = br.readLine().split(" ");
            for (int ii = 1; ii < N + 1; ii ++) {
                std[ii] = Integer.parseInt(selectList[ii - 1]);
                indegree[std[ii]] ++;
            }

            //then
            LinkedList<Integer> queue = new LinkedList<>();
            int answer = 0;

            for (int ii = 1; ii < N + 1; ii ++) {
                if (indegree[ii] == 0) queue.offer(ii);
            }

            while(!queue.isEmpty()) {
                int current = queue.poll();
                int next = std[current];
                indegree[next] -= 1;
                if (indegree[next] == 0) queue.offer(next);
                answer ++;
            }

            System.out.println(answer);
        }
    }
}
    https://www.acmicpc.net/source/28130292
    [プログラマ-Phython]フルナビゲーション
    Minixファイルシステム読書ノートのget_block