음악프로그램

백준 2623번: 음악프로그램

아이디어

위상 정렬을 하는 방법은 크게 두 가지가 존재한다.

1. DFS하고 거꾸로 출력하기
2. 진입 차수가 0인 노드를 계속 큐에 집어넣으면서 찾기

나는 1번 방법을 사용했다.
또 현재 DFS를 진행중인 노드를 만나는 경우 (아직 함수 실행이 끝나지 않은 노드) 사이클이 존재하는 것으로 판단하고 중간에 종료한다. 함수 실행이 완전히 종료된 노드는 finished[n]이 참일 것이다. visited[n]이 참이면서 finished[n]이 거짓인 경우는 사이클이 존재하는 경우이다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 1001;
int N, M;
vector<vector<int>> adj;
bool visited[MAX], finished[MAX];
stack<int> s;
bool cycle = false;

void dfs(int v) {
    visited[v] = true;
    for (int next : adj[v]) {
        if (!visited[next]) dfs(next);
        else if (!finished[next]) {
            cycle = true;
            return;
        }
    }
    s.push(v);
    finished[v] = true;
}

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

    cin >> N >> M;
    adj = vector<vector<int>>(N+1);
    for (int i = 0; i < M; i++) {
        int n;
        cin >> n;
        vector<int> v(n+1, 0);
        for (int i = 1; i < n+1; i++) {
            cin >> v[i];
            adj[v[i-1]].push_back(v[i]);
        }
    }

    for (int i = 1; i < N+1; i++) {
        if (!visited[i]) dfs(i);
    }
    if (cycle) cout << 0 << '\n';
    else {
        while(!s.empty()) {
            cout << s.top() << '\n';
            s.pop();
        }
    }

    return 0;
}

여담

그래프 사이클 찾기.. 까먹었다.. 흑흑.. 난 바보야..