728x90
위상 정렬이란 '순서가 정해져있는 작업' 을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다.
1. 집입차수가 0인 정점을 큐에 삽입합니다.
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입합니다.
4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복합니다. 모든 원소를 방문하기 준에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다.
m.blog.naver.com/ndb796/221236874984
<문제>
package Sort;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class LineUp {
static int n,m;
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());
HashMap<Integer, ArrayList<Integer>> mp = new HashMap<Integer, ArrayList<Integer>>();
Queue<Integer> q = new LinkedList<>();
int[] count = new int[n + 1];
for(int i=1; i<=n; i++){
mp.put(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());
mp.get(a).add(b);
count[b]++;
}
for (int i = 1; i <= n; i++) {
if(count[i]==0){
q.add(i);
}
}
while(!q.isEmpty()){
Integer num = q.poll(); //nullpoiner exception 없음
System.out.println(num + " ");
for (int j : mp.get(num)) {
count[j]--;
if( count[j] == 0){
q.add(j);
}
}
}
}
}