拓扑排序

[UNICKCHENG]

拓扑排序

待更新题库

[任务] 对一个有向无环图拓扑排序
[说明] 用一个队列实现,先把入度为0的点放入队列.然后考虑不断在图中删除队列中的点,每次删除一个点会产生一些新的入度为0的点.把这些点插入队列.
[接口]
bool toposort()
复杂度:O(|E|+|V|)
输入:
    n 全局变量,表示点数
    g 全局变量,g[i]表示从点i连出去的边
输出
    返回对给定的图,是否可以拓扑排序
    L 全局变量,拓扑排序的结果

const int maxn=100000+5;
vector<int> g[maxn];
int du[maxn],n,m,L[maxn];

bool toposort()
{
	memset(du,0,sizeof(du));
	for(int i=0;i<n;i++)
		for(int j=0;j<g[i].size();j++)
			du[g[i][j]]++;
	int tot=0;
	queue<int> Q;
	for(int i=0;i<n;i++) if(!du[i])Q.push(i);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		L[tot++]=x;
		for(int j=0;j<g[x].size();j++)
		{
			int t=g[x][j];
			du[t]--;
			if(!du[t])Q.push(t);
		}
	}
	if(tot==n) return 1;
	return 0;
}

题库

ID	TITLE	CODE(C/C++)	备注
POJ1094	Sorting It All Out	查看代码