[자바] 백준 2252번: 줄 세우기

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

위상정렬 알고리즘을 사용하면 된다.

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

public class P2252 {
	static int n,m;
	static int[] count;
	static LinkedList<Integer>[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		count= new int[n+1];
		arr=new LinkedList[n+1];
		
		for(int i=1;i<n+1;i++) {
			arr[i]=new LinkedList<>();
		}
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			count[b]++;
		}
		
		topsort();
		
	}
	
	static void topsort() {
		Queue<Integer> q= new LinkedList<>();
		
		for(int i=1;i<n+1;i++) {
			if(count[i]==0)
				q.add(i);
		}
		
		while(!q.isEmpty()) {
			int now=q.poll();
			System.out.print(now+" ");
			
			for(int j=0;j<arr[now].size();j++) {
				int next=arr[now].get(j);
				count[next]--;
				if(count[next]==0)
					q.add(next);
			}
		}
	}

}