【vijos】【拓扑排序】拓扑编号

描述

H国有n个城市，城市与城市之间有m条单向道路，满足任何城市不能通过某条路径回到自己。 现在国王想给城市重新编号，令第i个城市的新的编号为a[i]，满足所有城市的新的编号都互不相同，并且编号为[1,n]之间的整数。国王认为一个编号方案是优美的当且仅当对于任意的两个城市i,j，如果i能够到达j，那么a[i]应当

格式

输入格式

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

输出格式

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

样例1

样例输入1

5 4 4 1 1 3 5 3 2 5

样例输出1

2 3 5 1 4

分析

对一个有向无环图的拓扑排序满足如果i->j有一条边，在拓扑序中pos[i]

代码

#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> using namespace std; int in[100100],n,m,clock,ou[100100]; priority_queue<int> s; vector<vector<int> > edge(100010); vector<int> ans; void Kahn(){ while(!s.empty()){ int cur=s.top(); s.pop(); ans.push_back(cur); ou[cur]=clock--; //printf("%d ",cur); for(int i=0;i<edge[cur].size();i++){//vector遍历范式 in[edge[cur][i]]--; if(!in[edge[cur][i]]){ s.push(edge[cur][i]); } } } } int main(){ memset(in,0,sizeof(in)); scanf("%d%d",&n,&m); clock=n; for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); edge[y].push_back(x); in[x]++; } for(int i=1;i<=n;i++){ if(in[i]==0) { s.push(i); //printf("%d ",i); } } Kahn(); for(int i=1;i<=n;i++) printf("%d ",ou[i]); return 0; }

转载于:https://www.cnblogs.com/leotan0321/p/6081407.html