考前复习——拓扑排序

拓扑排序要解决的问题是给一个图的所有节点排序

在一个 DAG（有向无环图） 中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 u 到 v 的有向边 (u,v), 都可以有 u 在 v 的前面。

注:有环的图无法给出拓扑排序 因此也可以用这个性质判断图有无环

int n,m;
int in[N],out[N];//记录入度与出度
int num;
int ans[N];

queue<int> q;

struct node{
	int to,w,next;
}e[N];
int head[N];
int cnt;

void add(int u,int v,int w)
{
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}

int main()
{
	cin>>n>>m;//点 边
	for(int i=1;i<=n;i++)head[i]=-1;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		//由u至v
		//因此  u出度++  v入度++ 
		in[v]++;
		out[u]++;
		add(u,out[u],v);
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]==0)
		{
			//没有先决条件了 可以办掉它 
			q.push(i);
			num++;
			ans[num]=i;
		}
	}
	while(!q.empty())
	{
		int k=q.front();
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].next)
		{
			int t=e[i].w;
			in[t]--;
			if(in[t]==0)
			{
				q.push(t);
				num++;
				ans[num]=t;
			}
		}
	}
	/*
	num用于对特定位置的标识
	此处判断是因为--如果可以拓扑排序,那num==n 
	*/
	if(num==n)
	{
		for(int i=1;i<=num;i++)
			cout<<ans[i]<<" ";//拓扑排序输出 
	}
	else
	{
		cout<<"Error!";
	}
	return 0;
}