白準系譜復元家胡石(21276)

系譜復元家胡石

1.ヒント

住民たちはすべての祖先をよく覚えている。したがって、指定した情報を使用して作成できるツリーは1つだけです。

2）X→YXto YX→Yを逆に考え、YYからXXXまでの幹線と考える。これで、各レベルが000の頂点になると、各家族の始祖がわかるようになります。

3)位相整列を使用して高さ000の頂点を更新し、グラフィックを構成する場合は、ツリーのルートディレクトリから情報を下に表示できます。

2.近接

1) Map

昇順で出力するので、与えられた人の名前を並べ替えてみましょう.次に、(番号、、、名前)として保存します.Mapを処理(名前、、、番号)として宣言すると便利です.

3.実施

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		String[] S = new String[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = st.nextToken();
		Arrays.sort(S);
		// 이름이 주어지면 사전순으로 정렬했을 때 몇 번째인지 반환하는 map
		Map<String, Integer> m = new HashMap<>();
		for (int i = 0; i < N; i++) m.put(S[i], i);
		// 위상정렬을 위해 어떤 정점에 들어오는 간선의 개수 저장
		// X -> Y : X의 조상 중 Y가 있다
		// 가장 위에 있는 조상부터 고를 수 있도록 간선의 방향은 Y -> X가 됨
		int[] indegree = new int[N];
		boolean[][] adj = new boolean[N][N];
		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int u = m.get(st.nextToken());
			int v = m.get(st.nextToken());
			adj[v][u] = true;
			indegree[u]++;
		}
		// 들어오는 간선이 없는 정점은 시조
		int cnt = 0;
		for (int i = 0; i < N; i++)
			if (indegree[i] == 0) cnt++;
		bw.append(cnt).append("\n");
		Queue<Integer> q = new LinkedList<>();
		// 사전순으로 출력해야하므로 정렬된 배열 S의 순서에 맞게 큐에 삽입
		for (int i = 0; i < N; i++) if (indegree[i] == 0) {
			bw.append(S[i]).append(" ");
			q.offer(i);
		}
		bw.append("\n");
		// i번째 정점의 자식들을 사전순으로 정렬하기 위해서 우선순위 큐 사용
		ArrayList<PriorityQueue<Integer>> T = new ArrayList<>(N);
		for (int i = 0; i <= N; i++) T.add(new PriorityQueue<>());
		for (int i = 0; i < N; i++) {
			// indegree가 0인 가장 조상인 정점을 뽑는다
			int here = q.poll();
			for (int there = 0; there < N; there++) if (adj[here][there]) {
				indegree[there]--;
				// 새롭게 indgree가 0인 정점이 있으면 큐에 삽입
				// 마찬가지로 S는 정렬되어 있으므로 큐에는 오름차순으로 들어감
				if (indegree[there] == 0) {
					q.offer(there);
					T.get(here).offer(there);
				}
			}
		}
		for (int i = 0; i < N; i++) {
			bw.append(S[i]).append(" ");
			bw.append(T.get(i).size()).append(" ");
			PriorityQueue<Integer> pq = T.get(i);
			while (!pq.isEmpty()) bw.append(S[pq.poll()]).append(" ");
			bw.append("\n");
		}
		System.out.print(bw);
	}

}