(2252) 줄 세우기

https://www.acmicpc.net/problem/2252

단계별로 풀어보기

28단계(위상 정렬) 1번째

 

 

 

위상 정렬은 방향 그래프(DAG)를 방향성에 거스르지 않도록 순서대로 정렬하는 방법이다. 순서가 정해진 작업의 순서를 결정할 때 등에 사용된다.

그래프에 사이클이 있다면 위상 정렬할 수 없지만(무방향 그래프도 두 정점 사이에 사이클이 있는 것으로 생각할 수 있다), 보통 위상 정렬 알고리즘에서 위상 정렬 가능 여부(사이클 확인)도 알 수 있으므로 예외 처리만 해주면 된다.

크게 DFS와 스택을 사용하는 알고리즘과 큐를 사용하는 알고리즘으로 나뉘는데, 큐를 쓰는 방식을 선호한다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  queue<int> q;
  vector adj(n+1, vector<int>());
  vector<int> indegree(n+1), ans;
  
  while(m--){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    indegree[b]++;
  }
  
  for(int i=1;i<=n;i++){
    if(!indegree[i]){
      q.push(i);
    }
  }
  
  while(!q.empty()){
    int now= q.front();
    q.pop();
    
    ans.push_back(now);
    
    for(int next:adj[now]){
      if(!--indegree[next]){
        q.push(next);
      }
    }
  }
  
  for(int elem:ans)  cout << elem << " ";
  
  return 0;
}