π [λ°±μ€μκ³ λ¦¬μ¦ νμ΄] Q.2252 μ€ μΈμ°κΈ° λ¬Έμ νμ΄
π λ¬Έμ
https://www.acmicpc.net/problem/2252
Nλͺ μ νμλ€μ ν€ μμλλ‘ μ€μ μΈμ°λ €κ³ νλ€. κ° νμμ ν€λ₯Ό μ§μ μ¬μ μ λ ¬νλ©΄ κ°λ¨νκ² μ§λ§,
λ§λ ν λ°©λ²μ΄ μμ΄μ λ νμμ ν€λ₯Ό λΉκ΅νλ λ°©λ²μ μ¬μ©νκΈ°λ‘ νμλ€. κ·Έλλ§λ λͺ¨λ νμλ€μ λ€ λΉκ΅ν΄ λ³Έ κ²μ΄ μλκ³ , μΌλΆ νμλ€μ ν€λ§μ λΉκ΅ν΄ 보μλ€.
μΌλΆ νμλ€μ ν€λ₯Ό λΉκ΅ν κ²°κ³Όκ° μ£Όμ΄μ‘μ λ, μ€μ μΈμ°λ νλ‘κ·Έλ¨μ μμ±νμμ€.
π μ κ·Όλ²
boj Q.2252 μ€ μΈμ°κΈ° λ¬Έμ μ λλ€.
Nλͺ μ νμλ€μ μμ λ ν€ μμλλ‘ μ€μ μΈμμΌ νλ λ¬Έμ μ λλ€.
νμ§λ§ κ° νμλ€μ ν€κ° μ£Όμ΄μ§μ§ μκ³
μΌλΆ νμλ€κ° λΉκ΅ν΄ λ³Έ μ λ³΄λ§ μ£Όμ΄μ§λλ€.
μΌλΆ νμλ€κ°μ μ λ³΄λ‘ λκ° μμ μμΌνκ³ λ€μ μμΌ νλμ§κ°
μ£Όμ΄μ§κΈ° λλ¬Έμ μμμ λ ¬μ μ΄μ©ν΄μ
λ¬Έμ νμ΄κ° κ°λ₯ν©λλ€.
π» μ½λ
package problem.topological_sort;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main_2252 {
static StringBuilder sb = new StringBuilder();
static int n,m;
static List<List<Integer>> adjList ;
static int[] depth;
static Queue<Integer> queue = new LinkedList<>();
public static void main(String[] args) throws IOException {
input();
solve();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String temp[] = br.readLine().split(" ");
n = Integer.parseInt(temp[0]);
m = Integer.parseInt(temp[1]);
depth = new int[n+1];
adjList = new ArrayList<>();
for(int i=0; i<=n; i++){
adjList.add(new ArrayList<>());
}
for(int i=0; i<m; i++){
temp = br.readLine().split(" ");
int u = Integer.parseInt(temp[0]);
int v = Integer.parseInt(temp[1]);
adjList.get(u).add(v);
depth[v]++;
}
br.close();
}
private static void solve(){
for(int i=1; i<=n; i++){
if(depth[i]==0){
queue.offer(i);
}
}
while (! queue.isEmpty()){
int current = queue.poll();
sb.append(current+" ");
for(int next : adjList.get(current)){
depth[next]--;
if(depth[next] == 0){
queue.offer(next);
}
}
}
System.out.println(sb.toString());
}
}