题目描述:

N个小朋友,编号1∼N,要排成一队。

在安排每个人的顺序时,有M个要求,每个要求包含两个整数a和b,表示小朋友a要排在小朋友b的前面。

请你找出符合所有要求的排队顺序。

输入格式:

第一行包含两个整数N和M,表示小朋友的数量和要求的数量。

接下来M行,每行包含两个整数a和b,表示一个排队要求。

输出格式:

按排好队列从前到后的顺序在一行内输出每个小朋友的编号。

保证至少存在一个符合条件的顺序。

当符合条件的排队顺序不唯一时,编号更小的小朋友尽量更靠前。

数据范围:

  • 1≤N≤500
  • 1≤M≤5000
  • 1≤a,b≤N
  • 保证数对(a,b)各不相同。

输入样例:

4 3
1 2
2 3
4 3

输出样例:

1 2 4 3

题目分析: 拓扑排序,因为需要字典序最小,考虑使用优先队列。

代码实现:

#include <iostream>
#include <queue>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 1e3, M = 1e4;

int n, m, a, b, idx;
int h[N], e[M], ne[M], r[N];
bitset <N> bt;
vector <int> ans;
priority_queue <int, vector<int>, greater<int>> heap;
inline void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++, ++r[b]; 
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        add(a,b);
    }
    for (int i = 1; i <= n; ++i) {
        if (!r[i]) {
            bt[i] = 1;
            heap.push(i);
        }
    }
    while (!heap.empty()) {
        int i = heap.top(); heap.pop();
        ans.push_back(i);
        for (int t = h[i]; ~t; t = ne[t]) {
            int& j = e[t];
            --r[j];
            if (!r[j] && !bt[j]) {
                bt[j] = 1;
                heap.push(j);
            }
        }
    }
    for (auto& i : ans) cout << i << ' ';
    return 0;
}
分类: Top-Sort

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status