拓扑排序优化

之前就写过一篇关于拓扑排序的http://blog.csdn.net/monkey0le/article/details/7889725

今天参加某网络赛，其中有一题就是拓扑排序的，一看觉得开心，模板直接一放上去，TLE了，不开心。

后来才发现那种做法的复杂度是O(n^2)的，而且花费的空间也很大，于是做优化：

用临界表来保存每条边，拓扑排序的时候，把入度为0的点放入队列里面，同时，每次进行排序的时候，从队列里面取出入度为0的点，每次扩展也把入度为0的放进队列，于是把空间降到m，时间降到O(n+m)，m是又向边的数量。

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN=100000+50;
vector<int> map[MAXN];
int dis[MAXN];//保存每个点的入度
int num[MAXN];

int main()
{
    int n,m;
    int a,b;
	queue<int> q;
    while(scanf ("%d%d",&n,&m) != EOF)
    {
        memset(map,0,sizeof(map));
        memset(dis,0,sizeof(dis));
		int i;
		for (i = 1; i <= n; i++)
		{
			map[i].clear();
		}
        for(i=1;i<=m;i++)
        {
            scanf ("%d%d",&a,&b);
			map[a].push_back(b);
			dis[b]++;
        }
        int index;
		bool ok = true;
        int k=0;
		int cnt = 0;

		for (i = 1; i <= n; i++)
		{
			if (dis[i] == 0)
			{
				q.push(i);
				num[cnt++] = i;
			}
		}

		while (!q.empty())
		{
			int index = q.front();
			q.pop();
			for (int j = 0; j < map[index].size(); j++)
			{
				dis[map[index][j]]--;
				if (dis[map[index][j]] == 0)
				{
					q.push(map[index][j]);
					num[cnt++] = map[index][j];
				}
			}
		}

		if (cnt == n)
		{
			for(i=0;i<cnt;i++)
			{
				printf(i?" %d":"%d",num[i]);
			}
		}
		else
		{
			printf ("-1");
		}
		printf ("\n");
    }
	return 0;
}