백준 2252번: 줄 세우기 [위상정렬] - Java

https://www.acmicpc.net/status?user_id=change216&problem_id=2252&from_mine=1

 

 

<Java 코드>

 

진입차수를 기록하고, 진입차수가 0인 정점부터 탐색한다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
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) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		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());
		
		ArrayList<Integer> list[] = new ArrayList[N+1];
		int indegree[] = new int[N+1];
		boolean visit[] = new boolean[N+1];
		
		for (int i = 1; i < N+1; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			list[A].add(B);
			indegree[B]++;
		}
		
		Queue<Integer> q = new LinkedList<Integer>();
		for (int i = 1; i < N+1; i++) {
			if(indegree[i] == 0)
				q.add(i);
		}
		
		while(!q.isEmpty()) {
			int num = q.poll();
			System.out.print(num+" ");
			for(int n : list[num]) {
				indegree[n]--;
				if(indegree[n]==0)
					q.add(n);
			}
		}
		
		

	}

}