문제

풀이

1. pre 배열에는 본인보다 앞에서 서야 하는 학생의 수를 저장
2. v 배열은 학생이 줄에 섰는지 체크
3. post[i]에는 i번째 학생이 선행되어야 하는 학생들의 번호를 저장
4. pre[i]==0인 선행되어야 하는 학생 수가 0인 학생들을 반복적으로 확인해주며 모두 완료되면 종료

코드

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

public class Main {

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

        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());

        int[] pre=new int[n+1];
        int[] v=new int[n+1];
        ArrayList<Integer>[] post=new ArrayList[n+1];
        for(int i=1;i<n+1;i++)post[i]=new ArrayList<>();
        ArrayList<Integer> ans=new ArrayList<>();

        for(int i=0;i<m;i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            pre[b]++;
            post[a].add(b);
        }

        while(ans.size()!=n){
            for(int i=1;i<n+1;i++){
                if(v[i]==0 && pre[i]==0){
                    v[i]=1;
                    ans.add(i);
                    for(int a:post[i])pre[a]--;
                }
            }
        }

        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        for(int a:ans)bw.write(a+" ");
        bw.flush();
    }
}

#위상정렬