λ¬Έμ
Nλͺ μ νμλ€μ ν€ μμλλ‘ μ€μ μΈμ°λ €κ³ νλ€. κ° νμμ ν€λ₯Ό μ§μ μ¬μ μ λ ¬νλ©΄ κ°λ¨νκ² μ§λ§, λ§λ ν λ°©λ²μ΄ μμ΄μ λ νμμ ν€λ₯Ό λΉκ΅νλ λ°©λ²μ μ¬μ©νκΈ°λ‘ νμλ€. κ·Έλλ§λ λͺ¨λ νμλ€μ λ€ λΉκ΅ν΄ λ³Έ κ²μ΄ μλκ³ , μΌλΆ νμλ€μ ν€λ§μ λΉκ΅ν΄ 보μλ€. μΌλΆ νμλ€μ ν€λ₯Ό λΉκ΅ν κ²°κ³Όκ° μ£Όμ΄μ‘μ λ, μ€μ μΈμ°λ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
첫째 μ€μ N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)μ΄ μ£Όμ΄μ§λ€. Mμ ν€λ₯Ό λΉκ΅ν νμμ΄λ€. λ€μ Mκ°μ μ€μλ ν€λ₯Ό λΉκ΅ν λ νμμ λ²νΈ A, Bκ° μ£Όμ΄μ§λ€. μ΄λ νμ Aκ° νμ Bμ μμ μμΌ νλ€λ μλ―Έμ΄λ€. νμλ€μ λ²νΈλ 1λ²λΆν° Nλ²μ΄λ€.
μΆλ ₯
첫째 μ€μ νμλ€μ μμμλΆν° μ€μ μΈμ΄ κ²°κ³Όλ₯Ό μΆλ ₯νλ€. λ΅μ΄ μ¬λ¬ κ°μ§μΈ κ²½μ°μλ μ무거λ μΆλ ₯νλ€.
νμ΄
μμμ λ ¬μ λν λ¬Έμ μμ΅λλ€. νμλ€μ ν€λ₯Ό λΉκ΅νλλ° νμ¬ μμ κ³Ό κ°μ§ μμ μ¬λμ κΈ°μ€μΌλ‘ νμ λ£μ΄ λΉκ΅ν μ¬λμ 체ν¬ν΄μΌ ν©λλ€. μ΄λ κ² νλ©΄ μμ κ³Ό λΉκ΅κ° κ°λ₯ν μ¬λλ€λ§ νμ λ¨κ² λλλ°μ, μ΄λ₯Ό μΆλ ₯ν΄μ€μΌ ν©λλ€. λ°λΌμ νμ΄λ μλμ κ°μ΅λλ€.
public class Main {
static int n, m;
static int[] studens;
static int[] indegree;
static List<Integer>[] array;
public static void main(String[] args) throws Exception {
n = input.integer();
m = input.integer();
studens = new int[n + 1];
array = new ArrayList[n + 1];
indegree = new int[n + 1];
for (int index = 1; index <= n; index++) {
array[index] = new ArrayList<>();
}
for (int index = 0; index < m; index++) {
int studentX = input.integer();
int studentY = input.integer();
array[studentX].add(studentY);
indegree[studentY]++;
}
Queue<Integer> queue = new PriorityQueue<>();
for (int index = 1; index <= n; index++) {
if (indegree[index] == 0) {
queue.add(index);
}
}
while (!queue.isEmpty()) {
int pollStudent = queue.poll();
System.out.print(pollStudent + " ");
List<Integer> relationship = array[pollStudent];
for (int next : relationship) {
indegree[next]--;
if (indegree[next] == 0) {
queue.add(next);
}
}
}
}
'π PS > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
boj-1916 (0) | 2022.08.24 |
---|---|
boj-1850 (0) | 2022.07.23 |
boj-1922 λ€νΈμν¬ μ°κ²° (0) | 2022.07.19 |
boj-1744 μ λ¬ΆκΈ° (0) | 2022.07.15 |
boj-1300 Kλ²μ§Έ μ (0) | 2022.07.14 |
λκΈ