baekjoon 2252:줄 세우기

baekjoon 2252 줄 세우기

2252번 줄 세우기

접근

전형적인 위상정렬 문제이다.
CLRS책에서 본 기억을 되살려서 dfs end 시간으로 정렬하면 위상정렬이 된다는 것을 기억해내서
첫번째 방식에서는 그렇게 풀었다.
하지만 찾아보니 2번째 방식, indegree = 0인 vertex를 넣는 방식으로 위상정렬을 할 수 있다는 것을 알았다.
indegree=0인 vertex는 무조건 앞에 오기 때문에 넣어주고 접근과 동시에 자신의 adj vertex의 indegree를 하나씩 뺀다.
그리고 나서 또 indegree=0인 vertex접근을 반복한다. 만약 indegree=0인 vertex가 중간에 없는 단계가 나온다면
그래프가 dag가 아니라 cycle이 있다는 것을 의미한다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void dfsDag(int x, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& timeEnd);
int timeD = 0;
int main(){
  int n, m; cin >> n >> m;
  vector<vector<int>> adj(n);
  vector<int> timeEnd(n);
  fill(timeEnd.begin(), timeEnd.end(), 0);
  vector<bool> visited(n);
  while(m--){
    int a, b; cin >> a >> b;
    adj[a-1].push_back(b-1);
  }
  for(int i = 0; i < n; i++){
    if(!visited[i]){
      dfsDag(i, adj, visited, timeEnd);
    }
  }
  priority_queue<pair<int, int>> pq;
  for(int i = 0; i < n; i++){
    pq.push({timeEnd[i], i});
  }
  while(!pq.empty()){
    cout << pq.top().second+1 << " ";
    pq.pop();
  }
  
  
  return 0;
}
void dfsDag(int x, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& timeEnd){
  visited[x] = true;
  for(int i:adj[x]){
    if(visited[i]){
      continue;
    }
    dfsDag(i, adj, visited, timeEnd);
  }
  timeEnd[x] = timeD;
  timeD++;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
  int n, m; cin >> n >> m;
  vector<vector<int>> adj(n);
  vector<int> inDegree(n);
  for(int i = 0; i < m; i++){
    int a, b; cin >> a >> b;
    adj[a-1].push_back(b-1);
    inDegree[b-1]++;
  }
  vector<int> result;
  queue<int> q;
  for(int i = 0; i < n; i++){
    if(inDegree[i] == 0){
      q.push(i);
    }
  }
  while(!q.empty()){
    int x = q.front();
    q.pop();
    result.push_back(x+1);
    for(int i:adj[x]){
      inDegree[i]--;
      if(inDegree[i] == 0){
        q.push(i);
      }
    }
  }
  for(auto i : result){
    cout << i << " ";
  }
  
  
  return 0;
}

배운 점

topologicalSort 구현 해보았다.