아이디어

• 위상정렬 알고리즘을 사용한다. 자세한 설명은 여기 참고
  • 간선 연결을 끊을 때마다, 끝 정점보다 시작 정점의 Strahler 순서가 더 크면 끝 정점의 순서를 그걸로 갱신한다.
  • 간선 연결을 끊을 때마다, 끝 정점과 시작 정점의 Strahler 순서와 같으면 이전에 적어도 한 번은 그 순서와 같은 연결이 있었다는 뜻이므로, 정점의 진입차수가 0이 될 때 순서를 +1 해야 한다는 표시를 한다.
    • 만약 이후 더 큰 순서의 시작 정점이 있어 순서가 갱신되면 그 표시를 초기화한다.
• 최종적으로 M번 정점의 Strahler 순서가 정답이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int T, K, M, P, A, B;
	static List<List<Integer>> graph = new ArrayList<>();
	static int[] indeg;
	static int[] strahler;
	static boolean[] added;
	static Queue<Integer> q = new ArrayDeque<>();
	
	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t=1; t<=T; t++) {
			tk = new StringTokenizer(rd.readLine());
			K = Integer.parseInt(tk.nextToken());
			M = Integer.parseInt(tk.nextToken());
			P = Integer.parseInt(tk.nextToken());

			graph.clear();
			graph.add(null);
			for (int i=1; i<=M; i++) {
				graph.add(new ArrayList<>());
			}
			indeg = new int[M+1];
			strahler = new int[M+1];
			added = new boolean[M+1];
			
			for (int i=0; i<P; i++) {
				tk = new StringTokenizer(rd.readLine());
				A = Integer.parseInt(tk.nextToken());
				B = Integer.parseInt(tk.nextToken());
				graph.get(A).add(B);
				indeg[B]++;
			}
			
			for (int i=1; i<=M; i++) {
				if (indeg[i] == 0) {
					q.offer(i);
					strahler[i] = 1;
				}
			}
			
			while (!q.isEmpty()) {
				int x = q.poll();
				for (int n: graph.get(x)) {
					if (strahler[x] == strahler[n])
						added[n] = true;
					else if (strahler[x] > strahler[n]) {
						strahler[n] = strahler[x];
						added[n] = false;
					}
					indeg[n]--;
					if (indeg[n] == 0) {
						if (added[n]) strahler[n]++;
						q.offer(n);
					}
				}
			}
			
			sb.append(t).append(' ').append(strahler[M]).append('\n');			
		}
		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 14056 KB
• 시간: 124 ms

리뷰

• 체크 배열이 추가된 위상정렬, 어렵진 않았다.