문제 풀이(45)

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

import java.io.*;
import java.util.*;



class Node implements Comparable<Node>{
    int value;
    int count;

    Node(int value, int count)
    {
        this.value = value;
        this.count = count;
    }

    @Override
    public int compareTo(Node now)
    {
        if (now.value == this.value) {
            return now.count - this.count;
        }

        return now.value - this.value;
    }

    
}

public class Main {

   static int T, K, M, P;
   static ArrayList<Integer>[] A;
   static int[] indegree;
   static PriorityQueue<Node>[] pq;

   public static void main(String[] args) throws IOException {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    T = Integer.parseInt(br.readLine());

    while (T-- > 0) {
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken());

        M = Integer.parseInt(st.nextToken());

        pq = new PriorityQueue[M + 1];

        for (int i = 0; i <= M; i++) {
            pq[i] = new PriorityQueue<>();
        }

        A = new ArrayList[M + 1];

        indegree = new int[M + 1];

        for (int i = 0; i <= M; i++) {
            A[i] = new ArrayList<>();
        }

        P = Integer.parseInt(st.nextToken());
    
        for (int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());

            int S = Integer.parseInt(st.nextToken());

            int E = Integer.parseInt(st.nextToken());

            A[S].add(E);
            indegree[E]++;
        }

        Queue<Integer>Q = new LinkedList<>();

        for (int i = 1; i <= M; i++) {
            if (indegree[i] == 0) {
                pq[i].add(new Node(1, 1)); 
                Q.offer(i);
            }
        }


       while (!Q.isEmpty()) {
        
        int now = Q.poll();

        Node node = null;

        node = pq[now].peek();

        for(int next : A[now])
        {
            if(pq[next].isEmpty())pq[next].add(new Node(node.value, 0));

            if (pq[next].peek().value < node.value) {

                pq[next].add(new Node(node.value, 1));

            }else if (pq[next].peek().value == node.value) {   

                pq[next].add(new Node(pq[next].peek().value, pq[next].peek().count + 1));
            
            }

            indegree[next]--;

           

            if (indegree[next] == 0) {

                

                if (pq[next].peek().count > 1) {
                    pq[next].add(new Node(pq[next].peek().value + 1, 1));
                }

                Q.offer(next);
            }
        }
        
       }
       
        System.out.println(K+" "+pq[M].poll().value);
    }
    
   }
   
}