范沐垚


私信TA

用户名:dotcpp0614554

访问量:4473

签 名:

好大喜功

等  级
排  名 200
经  验 6481
参赛次数 0
文章发表 85
年  龄 18
在职情况 学生
学  校 看今夜 小楼灯宴
专  业 尽是良辰美眷

  自我简介:

沽名钓誉

//按拓扑排序排列 不断删除入度为0的节点 

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=110;

int h[N],e[N],ne[N],idx;
int d[N],q[N];
int n,hh=0,tt=-1;


void add(int a,int b)                     //初始化有向图 
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void pan()   //bool 
{
	for(int i=1;i<=n;i++)
	if(!d[i])
	q[++tt]=i;         //入度为0的节点入队 
	
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=h[x];i!=-1;i=ne[i])
		{
			int j=e[i];
			d[j]--;
			if(d[j]==0)
			q[++tt]=j;
		}
	}
	// return tt==n-1;    如果此图是拓扑排序,那么tt的值=n-1(所有节点均入队) 
}

int main(void)
{
	memset(h,-1,sizeof(h));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		while(cin>>x&&x)
		{
			add(i,x);
			d[x]++;
		}
	}
	pan();
	for(int i=0;i<n;i++)
	cout<<q[i]<<' ';
	return 0;
}


 

0.0分

0 人评分

  评论区