BOJ-2252 줄세우기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

dfs로 풀수 있지만. 위상정렬 공식으로 풀었다.

훕냐.. 공식.. 은 공식이다.

 

---

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

public class Solution {
	static int N, M;
	static int[] CNT;
	static ArrayList<Integer>[] VT;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long Start = System.currentTimeMillis();
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
				
		VT = new ArrayList[N+1];
		CNT = new int[N+1];
		
		for (int i = 1; i <= N; i++) {
			VT[i] = new ArrayList<Integer>();
		}
		
		int a, b;
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			VT[a].add(b);
			CNT[b]++;
		}
		
		Queue<Integer> q = new LinkedList<Integer>();
		for (int i = 1; i <= N; i++) {
			if(CNT[i]==0) q.add(i);
		}
		
		int cur;
		while (!q.isEmpty()) {
			cur = q.poll();
			System.out.print(cur+ " ");
			for (int n : VT[cur]) {
				if(--CNT[n]==0) q.add(n);
			}
		}
	}
}