토플로지 관련 줄세우기 문제.
원리 알고리즘은 알고리즘 내용 참조.

백준 Q2252

Sample Source Code


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

public class Main {

	public static void main(String[] args) {
		try {
			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[] line 		= new int[N+1];
			Queue<Integer> q= new LinkedList();
			ArrayList<Integer>[] al	= new ArrayList[N+1];
			for(int i=0;i<=N;i++)
				al[i] = new ArrayList();
			
			//System.out.format("N: %d M: %d \n",N,M);
			for(int i=0;i<M;i++) {
				st 	= new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				//System.out.format("%d %d \n",s,e);
				al[s].add(e);
				line[e]++; 
			}
			
			//line 이 0인 item을 q에 넣는다.
			for(int i=1;i<=N;i++) {
				if(line[i]==0) {
					q.add(i);
				}
			}
			
			while(!q.isEmpty()){
				int t = q.poll().intValue();
				
				//연결 선을 빼면서 line을 제거, 제거후에 0인경우 q에 입력
				for(int i=0; i < al[t].size() ; i++ ) {
					int sub = al[t].get(i).intValue();
					if(--line[sub] == 0 ){
						q.add(sub);
					}
				}				
				System.out.format("%d ", t);
			}
			
			//System.out.println(Arrays.toString(line));
			//System.out.println("End");
			
			
		}catch(Exception e) {
			e.printStackTrace();
		}	
	
	
	}
}

/*
입력
4 2
4 2
3 1

출력
3 4 1 2 

*/

참고