사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
위상 정렬은 항상 유일한 값으로 정렬되지 않음! 사이클이 없어야함!
진입 차수 = 자기 자신을 가리키는 에지의 개수
진입 차수 배열에서 진입 차수가 0인 노드를 선택하고
정렬 배열에 저장
그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수 1씩 뺌
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
학생들을 노드로 생각하고, 키 순서를 방향이 있는 에지로 생각하면 되겠네,
그리고 위상 정렬 하면 끝
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> arr;
vector<int> indegree;
arr.resize(n + 1);
indegree.resize(n + 1);
for (int i = 0; i < m; i++)
{
int s, e;
cin >> s >> e;
arr[s].push_back(e);
indegree[e]++;
}
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (indegree[i] == 0)
q.push(i);
}
while (!q.empty())
{
int now = q.front();
q.pop();
cout << now << '\n';
for (int next : arr[now])
{
indegree[next]--;
if (indegree[next] == 0)
q.push(next);
}
}
}
|
cs |