[백준 1766] 문제집

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

1766번: 문제집

 

줄 세우기에서 조~~금 변형된 문제

나는 queue에서 원소를 빼낼 때 값을 출력했으므로,

쉬운 문제를 먼저 푼다는 조건을 맞추기 위해 priorityqueue를 사용하였다.

그것만 수정해주면 됨..

 

 

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

class Main {
    static ArrayList<Integer> linkedlist[];
    static int indegree[];

    private static void trologySort() {
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i = 1; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            for (Integer e : linkedlist[vertex]) {
                if (--indegree[e] == 0)
                    queue.add(e);
            }
            System.out.print(vertex + " ");
        }
    }

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stk = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(stk.nextToken());   //문제의 수
        int M = Integer.valueOf(stk.nextToken());   //정보의 수

        //list
        linkedlist = new ArrayList[N+1];
        for (int i = 0; i <= N; i++)
            linkedlist[i] = new ArrayList<>();

        indegree = new int[N + 1];
        indegree[0] = -1;
        for (int i = 0; i < M; i++) {
            stk = new StringTokenizer(br.readLine());
            int start = Integer.valueOf(stk.nextToken());
            int end = Integer.valueOf(stk.nextToken());
            indegree[end]++;
            linkedlist[start].add(end);
        }
        trologySort();
    }
}