[題解]拓撲排序（優先隊列/字典序最小）

佚名 5年前 (2019-04-13) 随笔 1039人围观抢沙发百度已收录

考试抄书（日常）

P2038 -- 小叶子的故事之写代码

时间限制：1000MS 内存限制：131072KB

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题目描述(correct.cpp)

小叶子要写一道砍手题，要写N个函数。小叶子作为一名强迫症患者，喜欢按从上到下的顺序写函数，他会在写代码之前给要写的函数排个顺序依次完成。现在小叶子给你M个关系如(x,y),表示函数y要调用函数x（即函数x要写在函数y之前）。假设小叶子不会使用函数声明，请你设计一个字典序最小的序列。如果没法得到这样一个序列，则输出“OMG.”（没有引号）

输入格式(correct.in)

第一行有两个整数N，M。

接下来M行每行两个数x、y，表示x要写在y前面

输出格式(correct.out)

一行N个数，表示字典序最小的序列

样例输入

5 5

1 2

2 3

1 3

1 4

4 5

样例输出

1 2 3 4 5

数据规模与约定

对于 40% 的数据，N,M <= 5,000。

对于 100% 的数据，N,M <= 100,000。

裸的拓撲排序，字典序最小<=>把隊列換成優先隊列

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,m;
struct node{
    int v,nxt;
}e[maxn*2];
int head[maxn],cnt,tot;
int in[maxn],a[maxn];
void add(int u,int v){e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;}
void topo(){
    priority_queue<int,vector<int>,greater<int> >q;
    for(int i=1;i<=n;i++)
    if(in[i]==0)q.push(i);
    while(!q.empty()){
        int x=q.top();q.pop();
        a[++tot]=x;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].v;
            if(--in[y]==0)q.push(y);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);in[y]++;
    }
    topo();
    if(tot==n)
    for(int i=1;i<=tot;i++)
    printf("%d ",a[i]);
    else printf("OMG.");
}