[Vijos1790] 拓扑编号

2014-11-07
竞赛题解 / 图论
Vijos

描述 Description

H 国有 n 个城市，城市与城市之间有 m 条单向道路，满足任何城市不能通过某条路径回到自己。

现在国王想给城市重新编号，令第 i 个城市的新的编号为 a[i]，满足所有城市的新的编号都互不相同，并且编号为 [1,n] 之间的整数。国王认为一个编号方案是优美的当且仅当对于任意的两个城市 i,j，如果 i 能够到达 j，那么 a[i]应当 < a[j]。

优美的编号方案有很多种，国王希望使 1 号城市的编号尽可能小，在此前提下，使得 2 号城市的编号尽可能小… 依此类推。

输入格式 InputFormat

第一行读入 n,m，表示 n 个城市，m 条有向路径。
接下来读入 m 行，每行两个整数: x,y
表示第 x 个城市到第 y 个城市有一条有向路径。

输出格式 OutputFormat

输出一行: n 个整数
第 i 个整数表示第 i 个城市的新编号 a[i]，输出应保证是一个关于 1 到 n 的排列。

样例输入 SampleInput

5 4
4 1
1 3
5 3
2 5

样例输出 SampleOutput

2 3 5 1 4

Vijos 1790

代码 Code

反向建图，拓扑排序，每次标号最大值。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=100005;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
    int to,nx,vl;
}e[maxn*2];
int head[maxn],deg[maxn],ans[maxn];
priority_queue <int> q;
int cnt=0;
inline void ins(int u,int v)
{
    e[++cnt].to=v;e[cnt].nx=head[u];
    head[u]=cnt;
}
inline void find()
{
    int i,j,t,u,v,w;
    while (!q.empty()) q.pop();
    for (i=1;i<=n;i++) if (deg[i]==0) q.push(i);
    t=n;
    while (!q.empty())
    {
        u=q.top();q.pop();
        ans[u]=t--;
        for (i=head[u];i;i=e[i].nx)
        {
            v=e[i].to;
            deg[v]--;
            if (deg[v]==0) q.push(v);
        }
    }
    for (i=n;i>0;i--) if (ans[i]==0) ans[i]=t--;
}
int main()
{
    memset(deg,0,sizeof(deg));
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        ins(y,x);
        deg[x]++;
    }
    find();
    for (i=1;i<n;i++) printf("%d",ans[i]);
    printf("%d\n",ans[n]);
    return 0;
}