백준 9470 : Strahler 순서

https://www.acmicpc.net/problem/9470

9470번: Strahler 순서

[ 문제풀이 ]

기본적인 위상 정렬에 각 노드의 order만 관리해주면 쉽게 해결할 수 있는 문제이다.

order의 조건이 2개이기 때문에 count 배열을 하나 선언하여 같은 값이 진입할 경우 개수를 저장해준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int K, M, P;
	static int[] inDegree, order, count;
	static List<Integer>[] edges;
	static Queue<Integer> q;
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			inDegree = new int[1001];
			order = new int[1001];
			count = new int[1001];
			q = new LinkedList<>();
			edges = new ArrayList[1001];
			for (int i = 0; i <= 1000; ++i) edges[i] = new ArrayList<>();
			
			int T = Integer.parseInt(br.readLine());
			while (T-- > 0) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				K = Integer.parseInt(st.nextToken());
				M = Integer.parseInt(st.nextToken());
				P = Integer.parseInt(st.nextToken());
				for (int i = 0; i < P; ++i) {
					st = new StringTokenizer(br.readLine());
					int A = Integer.parseInt(st.nextToken());
					int B = Integer.parseInt(st.nextToken());
					edges[A].add(B);
					inDegree[B]++;
				}
				
				topologySort();
				bw.write(K + " " + getMax() + "\n");
				init();
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void init() {
		for (int i = 0; i <= M; ++i) {
			edges[i].clear();
			inDegree[i] = 0;
			order[i] = 0;
			count[i] = 0;
		}
	}
	
	public static void topologySort() {
		for (int i = 1; i <= M; ++i) {
			if (inDegree[i] == 0) {
				order[i] = 1;
				q.offer(i);
			}
		}
		
		while (!q.isEmpty()) {
			int v = q.poll();
			
			for (int nv : edges[v]) {
				if (order[nv] < order[v]) {
					order[nv] = order[v];
					count[nv] = 1;
				} else if (order[nv] == order[v]) {
					count[nv]++;
				}
				
				if (--inDegree[nv] == 0) {
					order[nv] += count[nv] >= 2 ? 1 : 0;
					q.offer(nv);
				}
			}
		}
	}
	
	public static int getMax() {
		int max = -1;
		for (int i = 1; i <= M; ++i) {
			max = Math.max(max, order[i]);
		}
		return max;
	}
}