백준 2252번: 줄 세우기

문제

문제 바로가기> 백준 2252번: 줄 세우기

풀이

위상정렬을 이용해서 문제를 풀었다.
Topology sort(위상정렬): 순서가 있는 작업을 차례대로 수행할 때 순서를 결정해주기 위한 알고리즘

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

int n, m, indegree[32001]{};
vector<int> edge[32001];

void topologySort(){
    queue<int> q, ans;
    for(int i=1; i<=n; i++){
        if(indegree[i]==0){
            q.push(i);
            ans.push(i);
        }
    }
    while (1){
        if(q.empty()) break;
        int x = q.front(); q.pop();
        for(int i=0; i<edge[x].size(); i++){
            indegree[edge[x][i]]--;
            if(indegree[edge[x][i]]==0){
                q.push(edge[x][i]);
                ans.push(edge[x][i]);
            }
        }
    }
    for(int i=1; i<=n; i++) {
        cout << ans.front() << ' '; ans.pop();
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int a, b; cin>>a>>b;
        edge[a].push_back(b);
        indegree[b]++;
    }
    topologySort();
}