2835_字典序_堆

发布于 2017-11-07  907 次阅读

题目描述

你需要构造一个1~n的排列，使得它满足m个条件，每个条件形如(ai,bi)，表示ai必须在bi前面。在此基础上，你需要使它的字典序最小。

思路

我们对有冲突的点连边，如果一个点的入度为0那么他就是一个可以放在任意位置的点，我们用一个堆来每次取出最小的值，然后用类似拓扑的方式进行处理

 

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y)) 
#define N 100001
#define LL long long
struct edge
{
    int to, next;
}e[N];
int in[N], ls[N], n, m;
priority_queue, greater > q;
inline LL read()
{
    LL x = 0, p = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') p = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
    return x * p;
}
int ans[N], l = 0;
int bfs()
{
    while (!q.empty())
    {
        ans[++l] = q.top();
        int now = q.top();
        q.pop();
        for (int i = ls[now]; i; i = e[i].next)
        {
            in[e[i].to]--;
            if (in[e[i].to] == 0)
                q.push(e[i].to);
        }
    }
}
int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= m; i++)
    {
        int x = read(), y = read();
        e[i] = (edge){y, ls[x]};
        ls[x] = i;
        in[y]++;
    }
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);
    bfs();
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
}

 

]]>