P15915 题解

Zelda_max · 2026-03-27 20:57:09 · 题解

一道拓扑排序的模板题，不会请先完成拓扑排序模板题。

这道题我们可以抽象成一个有 n 个点，m 条边的有向图，并用一个 bfs 来求这个图的拓扑排序，为了保证字典序最小，我们同时需要用单调队列来维护。

奉上代码：

#include<bits/stdc++.h>
using namespace std;
int cnt[100001];
vector<int> adj[100001];
queue<int> q;
priority_queue<int, vector<int>, greater<int>> pq;
void bfs() {
    //拓扑排序
    while(!pq.empty()) {
        int u = pq.top();
        pq.pop();
        q.push(u);
        for(int k : adj[u]) {
            cnt[k]--;
            if(cnt[k] == 0) {
                pq.push(k);
            }
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        //来记录这个点的入度
        cnt[v]++;
    }
    for(int i = 1; i <= n; i++) {
        if(cnt[i] == 0) {
            pq.push(i);
        }
    }
    bfs();
    //如果队列长度不等于n说明未能完成所有工程
    if(q.size() != n) cout << "IMPOSSIBLE";
    else {
        //输出
        while(!q.empty()) {
            cout << q.front() << ' ';
            q.pop();
        }
    }
    return 0;
}