<링크>
https://www.acmicpc.net/problem/2252
<소스코드>
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 | #include<stdio.h> #include<vector> #include<queue> using namespace std; vector<int> adj[32001]; queue<int> q; int indegree[32001]; int main() { int N, M; scanf("%d%d", &N, &M); while (M--) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(b); ++indegree[b]; } for (int i = 1; i <= N; ++i) if (indegree[i] == 0) q.push(i); while (!q.empty()) { int c = q.front(); printf("%d ", c); q.pop(); for (int i : adj[c]) { --indegree[i]; if (indegree[i] == 0) q.push(i); } } } | cs |
<풀이>
차수를 기록하고 차수가 0인애들을 싹 큐에 집어넣는다.
큐에서 하나씩 빼면서 그 노드와 연결된 애들의 차수를 줄여주고, 차수가 0이되면 금마를 큐에 집어넣는다.