Topological Sort Summary

1.用途：可以判断有向图（➀可以存在孤立结点➁也可以有重边）是否存在环。

2.代码模板：

  1）顶点少于1000的图可以用邻接矩阵来存储：

➀用STL中的栈略耗时，但代码量略少

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#define Max(a,b) ((a)>(b)?(a):(b))
#define N 1005
using namespace std;

int mat[N][N];
int in[N];
int n,m;

void Topo()
{
	int i,j;
	stack<int> S;
	for(i=0;i<n;i++)
	{
		if(in[i]==0)
		{
			S.push(i);
			in[i]=-1;
		}
	}
	int cnt=0;
	while(!S.empty())
	{
		i=S.top();
		S.pop();
		cnt++;
		for(j=0;j<n;j++)
		{
			in[j]-=mat[i][j];
			if(in[j]==0)
			{
				S.push(j);
				in[j]=-1;
			}
		}
	}
	if(cnt==n)
		printf("YES\n");
	else
		printf("NO\n");
}

int main()
{
	int i;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		memset(in,0,sizeof(in));
		memset(mat,0,sizeof(mat));
		for(i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			mat[a][b]++;
			in[b]++;
		}
		Topo();
	}
	return 0;
}
           

➁用数组模拟的栈略省时

#include<iostream>
#include<cstdio>
#include<cstring>
#define Max(a,b) ((a)>(b)?(a):(b))
#define N 1005
using namespace std;

int mat[N][N];
int in[N];
int n,m;
int Stack[N],top;

void Topo()
{
	int i,j;
	top=0;
	for(i=0;i<n;i++)
	{
		if(in[i]==0)
		{
			Stack[++top]=i;
			in[i]=-1;
		}
	}
	int cnt=0;
	while(top!=0)
	{
		i=Stack[top--];
		cnt++;
		for(j=0;j<n;j++)
		{
			in[j]-=mat[i][j];
			if(in[j]==0)
			{
				Stack[++top]=j;
				in[j]=-1;
			}
		}
	}
	if(cnt==n)
		printf("YES\n");
	else
		printf("NO\n");
}

int main()
{
	int i;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		memset(in,0,sizeof(in));
		memset(mat,0,sizeof(mat));
		for(i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			mat[a][b]++;
			in[b]++;
		}
		Topo();
	}
	return 0;
}
           

2）顶点少于1000的图可以用邻接表来存储：

➀用STL中的vector模拟略耗时，但代码量略少

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;

vector<int> vec[105];
int n,m;
int in[105];

void Topo()
{
	int i,j;
	stack<int> S;
	for(i=0;i<n;i++)
	{
		if(in[i]==0)
		{
			S.push(i);
			in[i]=-1;
		}
	}
	int cnt=0;
	while(!S.empty())
	{
		i=S.top();
		S.pop();
		cnt++;
		for(j=0;j<vec[i].size();j++)
		{
			int k=vec[i][j];
			in[k]--;//和邻接矩阵不同
			if(in[k]==0)
			{
				S.push(k);
				in[k]=-1;
			}
		}
	}
	if(cnt==n)
		printf("YES\n");
	else
		printf("NO\n");
}

int main()
{
	int i;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		memset(in,0,sizeof(in));
		for(i=0;i<n;i++)
		{
			vec[i].clear();
		}
		for(i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			in[b]++;
			vec[a].push_back(b);//重边也包括进去了，形式与邻接矩阵不同
		}
		Topo();
	}
	return 0;
}
           

➁用链表写邻接表代码较多，不适合于比赛和考试，此处就省略了。