백준/2623번/음악프로그램/골드3

Problem Link: https://www.acmicpc.net/problem/2623

문제 설명

Site: Baekjoon
Number: 2623
Category: Topology Sort
Rank: Gold 3

숫자들의 순서가 여러개 주어졌을 때, 이를 모두 만족하는 순서가 존재한다면 그 중 하나를 출력하고 존재하지 않는다면 0을 출력하는 문제입니다.

문제 풀이

전형적인 위상 정렬 문제로 여타 다른 위상정렬 문제와 같은 방식으로 해결할 수 있습니다.

주어지는 숫자의 순서를 방향으로 넣고, 그렇게 방향으로 들어올 때 마다 차수를 하나 씩 늘려줍니다.

이 후에 차수가 0인 요소들을 판별큐와 정답큐에 넣으며 판별큐가 빌 때까지 진행하고, 판별 큐에 있는 갯수가 가수의 갯수와 동일하다면 순서가 존재하니 순서를 출력하고, 아니라면 존재하지 않는 것이므로 0을 출력합니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool visited[1002];

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

    int N, M;
    cin >> N >> M;

    vector<vector<int>> edges(N+1, vector<int>());
    vector<int> degrees(N+1, 0);

    for(int i = 0; i < M; i++)
    {
        int num;
        cin >> num;

        int before, current;
        cin >> before;
        for(int j = 1; j < num; j++)
        {
            cin >> current;

            edges[before].push_back(current);
            degrees[current]++;
            before = current;
        }
    }

    queue<int> q, ans;

    for(int i = 1; i < N+1; i++)
    {
        if (degrees[i] == 0)
        {
            q.push(i);
            visited[i] = true;
            ans.push(i);
        }
    }

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();

        for(int i = 0; i < edges[cur].size(); i++)
        {
            if (visited[edges[cur][i]] == true)
                continue;

            if (--degrees[edges[cur][i]] == 0)
            {
                q.push(edges[cur][i]);
                ans.push(edges[cur][i]);
            }
        }
    }

    if(ans.size() == N)
    {
	    while(!ans.empty())
	    {
            cout << ans.front() << '\n';
            ans.pop();
	    }
    }
    else
    {
        cout << 0;
    }

    return 0;
}