백준) 1766 문제집

문제집

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

위상정렬 문제.

다만 스페셜 저지가 아닌만큼, 같은 위상이라도 특수조건이 주어진다.

예제의 경우에, 3과 4는 같은 위상이지만, 조건3에 의해 3이 더 쉬운문제이므로 3을 먼저 풀어야 한다.

이제 3이 없어졌으니까(3이 뿜는 간선도 사라졌다) 문제 4와 1은 같은 위상이다. 조건 3에 의해 1을 먼저 푼다.

즉 큐는 큐지만, 문제 번호가 낮은 걸 먼저 pop해줄 자료구조로 우선순위 큐를 쓰면 풀 수 있다.

heap을 만들어서 풀어봤지만 속도는 같았다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, a, b;
int in[32001];
 
struct heap {
    int* arr;
    int cnt = 0;
 
    heap(int n) { arr = new int[n]; }
    ~heap() { delete[] arr; }
 
    void swap(int& a, int& b) {
        int t = a; a = b; b = t;
    }
 
    void push(int x) {
        ++cnt;
        arr[cnt] = x;
        int v = cnt;
 
        while (v / 2 >= 1 && arr[v/2] > arr[v]) {
            swap(arr[v], arr[v / 2]);
            v /= 2;
        }
    }
 
    void pop() {
        arr[1] = arr[cnt];
        cnt--;
 
        int v = 1;
        while (v * 2 <= cnt) {
            int iv = v * 2;
            if (iv + 1 <= cnt && arr[iv] > arr[iv + 1])
                iv++;
            if (arr[v] > arr[iv]) {
                swap(arr[v], arr[iv]);
                v = iv;
            }
            else
                break;
        }
    }
    int top() { return arr[1]; }
    bool empty() { return cnt == 0; }
};
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        in[b]++;
    }
 
    //priority_queue<int> pq;
    heap pq(n + 1);
    for (int i = 1; i <= n; ++i)
        if (!in[i])
            pq.push(i);
 
    while (!pq.empty()) {
        int t = pq.top();
        printf("%d ", t);
        pq.pop();
 
        for (auto next : edge[t]) {
            in[next]--;
            if (in[next] == 0)
                pq.push(next);
        }
    }
 
    return 0;
}