(BOJ) 2623 풀이

#include<bits/stdc++.h>

using namespace std;
queue<int> q;
int in_degree[1001];
vector<int> v[1001];
queue<int> s;
int main(){
    int N,M;
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> N >> M;
    int num,a,b;
    int tmp=0;
    for(int i=1;i<=M;i++){
        cin >> num;
        cin >> a;
        for(int j=1;j<=num-1;j++){
            cin >> b;
            v[a].push_back(b);
            in_degree[b]++;
            a=b;
        }
    }
    for(int i=1;i<=N;i++){
        if(in_degree[i]==0)q.push(i);
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        s.push(t);
        for(auto i: v[t]){
            if(--in_degree[i]==0){
                q.push(i);
            }
        }
    }
    if(s.size()!=N){
        cout << 0 << endl;
    }else{
        for(int i=0;i<N;i++){
            cout << s.front() << '\\n';
            s.pop();
        }
    }
}

위상정렬문제인데, 문제조건에서 DAG 라고 주어지지 않아 DAG 인지 판단해야한다.

BFS 를 돌 때 바로 출력하지 않고, answer queue 에 넣어놨다가

사이클이 있는 경우에는 똑같은 번호를 answer queue 에 넣어서

N 보다 queue 의 size 가 커지기 떄문에 분기처리해주면 된다.

6 3
3 1 4 3
4 6 2 5 4
2 2 3

입력이 이런식으로 주어지는데, 맨 앞에 것을 먼저 입력받고 (1,6,2)

변수에 저장해놨다가 2개씩 연결해주면 된다.

1→4, 4→3 / 6 → 2, 2 →5, 5→4 /