(C++) 백준 2252번 - 줄 세우기

문제 링크 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

풀이

indegree라는 자신에게 들어오는 간선의 수를 저장하는 배열을 사용하여, indegree가 0인 경우에만 큐에 넣어 출력하는 방식으로 풀이하였다.

indegree가 0이 아닌 경우에는 연결된 정점을 방문할 때마다 indegree를 1씩 줄여나가며, 0이 되는 순간 큐에 들어가도록 한다.

#include <iostream>
#include <queue>

using namespace std;

vector<int> students[32005];
int indegree[32005];
queue<int> q;
int n, m, fs, ss;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    while(m--)
    {
        cin >> fs >> ss;
        students[fs].push_back(ss);
        indegree[ss]++;
    }
    for(int i = 1; i <= n; i++){
        if(!indegree[i]) q.push(i);
    }
    while(!q.empty()){
        int v = q.front();
        cout << v << " ";
        q.pop();
        for(auto k : students[v]){
            indegree[k]--;
            if(!indegree[k]) q.push(k);
        }
    }
}