洛谷 （模板）P3644 普及-

B3644 【模板】拓扑排序 / 家谱树 - 洛谷 (luogu.com.cn)

卡恩bfs

#include<bits/stdc++.h>
#define int long long 
using namespace std;
bool tin=0;
vector <int> h[1005],tp;//h存图，tp存答案序列 
int din[1005],n;//din存入度 
bool b()
{
	queue<int> q;//队列存入度为0的点，若想要节点编号最小换成优先队列 
	for(int i=1;i<=n;i++)
	if(!din[i])
	q.push(i);//入度为0全进去 
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(auto y:h[x])
		{
			if(--din[y]==0)//删点存数 
			q.push(y);
		}
		tp.push_back(x);
	}
	if(tp.size()==n)//无环，所有点入 
	return 1;
	else//有环，数量不够 
	return 0;
}
void solve()
{
	int t;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		while(1)
		{
		cin>>t;
		if(!t)
		break;
		h[i].push_back(t);//存图 
		din[t]++;//存入度 
	}
	}
	if(b())
	{
		for(auto x:tp)//输出 
		cout<<x<<' ';
	}
	else//有环 
	cout<<"-1";
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int T=1;
	if(tin)
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

变色dfs

#include<bits/stdc++.h>
#define int long long 
using namespace std;
bool tin=0;
vector <int> h[1005],tp;//存图，存答案 
int c[1005];//0表示没便利过，-1表示正在便利，1表示结束 
bool dfs(int x)
{
	c[x]=-1;//正在遍历 
	for(auto y:h[x])
	{
		if(c[y]==-1)//遇到正在遍历的了，环 
		return 0;
		else if(c[y]==0)
		{
			if(!dfs(y))//遇到新的再去遍历 
			return 0;
		}
	}
	c[x]=1;
	tp.push_back(x);//结束，存值，返回运行正确 
	return 1;
}
void solve()
{
	int n,x;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		c[i]=0;//重置 
		while(1)
		{
			cin>>x;
			if(!x)
			break;
			h[i].push_back(x);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!c[i])
		{
			if(!dfs(i))
			{
				cout<<"-1";//有问题 
				return ;
			}
		}
	}
	reverse(tp.begin(),tp.end());//这个方法求出来是反的 
	for(auto x:tp)
	cout<<x<<" ";
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int T=1;
	if(tin)
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}