学步园

最小拓扑序

topsort.pas/c/cpp

1s/64MB

【题目描述】

给一个有向无环图，求其字典序最小的拓扑序。

一个拓扑序被认为字典序{pi}最小当且仅当对于任何其他拓扑序{qi}，均存在正整数k，使得对于所有i<k有pi=qi且pk<qk。

【输入】

输入第一行包含两个数n, m分别表示有向无环图的点数和边数。

接下来m行，每行两个数ai, bi，表示图中存在一条ai指向bi的有向边。

【输出】

输出n个数，每个数用空格隔开，表示该图的拓扑序。

【输入样例】

3 1

2 1

【输出样例】

2 1 3

【样例解释】

2, 1, 3

2, 3, 1

3, 2, 1

均为合法拓扑序，但是2, 1, 3为最小字典序的拓扑序。

【数据规模】

50%的数据满足：n<=1000

100%的数据满足：1<=n<=100000, 1<=m<=100000, 1<=ai,bi<=n

保证数据至少存在一种合法的拓扑序列

完成情况（cena测评）

这一题求拓扑序很容易，但是题目多了一个要求，字典序最小

其实这个要求我们在无形中已经达到了，先看看O(N*N)的算法

for(int i=1;i<=n;i++)
	if(deg[i]==0)
	{
		printf("%d ",i);
		for(int j=1;j<=n;j++)
			if(map[i][j]) deg[j]--;
	}

这样输出来的就肯定是按照字典序的！

因为我们只要保证每次找入度为0的点的序号最小，那么我们就能保证整个字典序最小

但是这样是显然要超时的，我们可以用队列优化（栈什么的也可以）

先看看上面的代码，j 循环是不能省掉的（因为必须要删边）

但是我们看看最外层的 i 循环，是找入度为 0 的点，那么我们的优化就要在这上面做文章了

我们在队列里存下所有入度为0的点，每一次就取队首，然后一个循环删边即可，这样就可以搞掉外面的一重 i 循环了

至于保证字典序最小，很简单，把队列改成优先队列（堆）就ok！

C++ AC Code

/*http://blog.csdn.net/jiangzh7
By Jiangzh*/
#include<cstdio>
#include<queue>
using namespace std;
const int N=100000+10;
const int inf=0x3f3f3f3f;

int n,m;
struct link{int y;link *next;}*head[N];
int deg[N];
priority_queue<int,vector<int>,greater<int> > Q;

void inlink(int x,int y)
{
	link *node=new link;
	node->y=y;node->next=head[x];
	head[x]=node;
}

void read()
{
	freopen("topsort.in","r",stdin);
	freopen("topsort.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		inlink(x,y);deg[y]++;
	}
}

void work()
{
	for(int i=1;i<=n;i++) if(deg[i]==0) Q.push(i);
	while(!Q.empty())
	{
		int j=Q.top();Q.pop();
		printf("%d ",j);deg[j]=inf;
		for(link *node=head[j];node;node=node->next)
		{
			deg[node->y]--;
			if(!deg[node->y]) Q.push(node->y);
		}
	}
}
		
int main()
{
	read();
	work();
	return 0;
}