백준: Class 5 - 1766, 2252, 2623

</br> 클래스 5 계속
</br>

1766: 문제집

https://www.acmicpc.net/problem/1766

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }

    priority_queue<int, vector<int>, greater<>> pq;
    for(int i = 1; i <= n; i++){
        if( ind[i] == 0 ) pq.push(i);
    }

    while( pq.size() ){
        int now = pq.top();
        pq.pop();
        cout << now << ' ';
        for(int i = 0; i < v[now].size(); i++){
            int nx = v[now][i];
            ind[nx]--;
            if( ind[nx] == 0 ) pq.push(nx);
        }
    }
    cout << '\n';

위상 정렬 어게인
전 포스트(9466: 텀 프로젝트, https://cyj893.github.io/algorithm/Algorithm17_9/)와 거의 비슷하지만, 이번엔 쉬운 문제(앞 번호)부터 풀어야 한다는 조건이 있으므로, 우선순위 큐로 저장해서 출력해 보니까 딱 되더라
</br>

2252: 줄 세우기

https://www.acmicpc.net/problem/2252

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }

    queue<int> q;
    for(int i = 1; i <= n; i++){
        if( ind[i] == 0 ) q.push(i);
    }

    while( q.size() ){
        int now = q.front();
        q.pop();
        cout << now << ' ';
        for(int i = 0; i < v[now].size(); i++){
            int nx = v[now][i];
            ind[nx]--;
            if( ind[nx] == 0 ) q.push(nx);
        }
    }
    cout << '\n';

또 위상 정렬
이건 또 윗 문제 코드에서 우선순위 큐를 써도 되고 안 써도 되고
그냥 같은 코드 제출해도 상관없음
</br>

2623: 음악프로그램

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

    for(int i = 0; i < m; i++){
        int d;
        cin >> d;
        vector<int> t;
        for(int j = 0; j < d; j++){
            int a;
            cin >> a;
            t.push_back(a);
            for(int k = 0; k < t.size()-1; k++){
                if( v[t[k]].count(a) ) continue;
                v[t[k]].insert(a);
                ind[a]++;
            }
        }
    }

    queue<int> q;
    for(int i = 1; i <= n; i++){
        if( ind[i] == 0 ) q.push(i);
    }

    queue<int> ans;
    while( q.size() ){
        int now = q.front();
        q.pop();
        ans.push(now);
        for(int nx : v[now]){
            ind[nx]--;
            if( ind[nx] == 0 ) q.push(nx);
        }
    }

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

어째 이 포스트는 위상 정렬 세트가 되었다
일단 입력 받을 때, 가능한 모든 순서를 다 저장한다. 중복이 있을 수 있으므로 이번엔 인접 리스트로 set을 사용했다.

ex) 순서가 1 2 3 4 5라면 1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5를 저장

그리고 또 큐를 다 비우면 된다
예외로 얘는 답이 없는 경우가 있으므로 주의하세요

ex)
pd1: 1 2
pd2: 2 1

</br>

---

위상 정렬 굿
</br>