[JAVA] 순서가 있는 트리에서 위상정렬

 

단, 비순환 그래프임이 가정되어야 함.

 

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

public class 작업순서 {
	static ArrayList <Integer> as;
	static int n;
	static int m;
	static int [] visited;
	static int [] count;
	static ArrayList<Integer> [] al;
	
	public static void topo() {
		ArrayList <Integer> q = new ArrayList<>();
		for(int i=1;i<n+1;i++) {
			if(count[i]==0) {
				q.add(i);
				visited[i]=1;
			}
		}
		
		while(q.size()!=0) {
			int num = q.remove(0);
			as.add(num);
			
			for(int i=0;i<al[num].size();i++) {
				count[al[num].get(i)]-=1;
				if(count[al[num].get(i)]==0 && visited[al[num].get(i)]==0) {
					q.add(al[num].get(i));
					visited[al[num].get(i)]=1;
				}
			}
		}
	}
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for(int t=1;t<=10;t++) {
			String [] str= br.readLine().split(" ");
			n = Integer.parseInt(str[0]);
			m = Integer.parseInt(str[1]);
			
			al = new ArrayList[n+1];
			as = new ArrayList<>();
			
			for(int i=0;i<n+1;i++) {
				al[i] = new ArrayList<Integer>();
			}
			
			count = new int[n+1];
			visited = new int[n+1];
			
			String [] str_arr = br.readLine().split(" ");
			for(int i=0;i<2*m;i=i+2) {
				al[Integer.parseInt(str_arr[i])].add(Integer.parseInt(str_arr[i+1]));
				count[Integer.parseInt(str_arr[i+1])] += 1;
			}
			
			topo();
			System.out.print("#"+t);
			for(int i=0;i<as.size();i++) {
				System.out.print(" "+as.get(i));
			}
			System.out.println();
		}
		
	}

}