D01 拓扑排序

// 拓扑排序 Kahn算法 O(V+E)
#include<bits/stdc++.h>
using namespace std;

const int N=110;
int n,rd[N];
vector<int> e[N],tp;

bool topo(){
  queue<int> q;
  for(int i=1; i<=n; i++) if(!rd[i]) q.push(i); //入度为0的点均入队
  while(q.size()){
    int u=q.front(); q.pop(); //出队
    tp.push_back(u); //记录拓扑序
    for(auto v:e[u]) if(--rd[v]==0) q.push(v); //入队
  }
  return tp.size()==n;
}
int main(){
  cin>>n;
  for(int i=1,j; i<=n; i++){
    while(cin>>j,j){
      e[i].push_back(j);
      rd[j]++; //入度
    }
  }
  topo();
  for(int i=0; i<n; i++) cout<<tp[i]<<" ";
}

#include<bits/stdc++.h>
using namespace std;
#define N 110
vector<int>e[N];
int rd[N],a[N][N];
queue<int>q; 
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int j=0;
		while(1)
		{
			scanf("%d",&a[i][++j]);
			if(!a[i][j])break;
			e[i].push_back(a[i][j]);
			rd[a[i][j]]++;
		}
	}
	for(int i=1;i<=n;i++)
		if(rd[i]==0)q.push(i),printf("%d ",i);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int y:e[x])
		{
			rd[y]--;
			if(!rd[y])q.push(y),printf("%d ",y);
		}
	}
	return 0;
}

dfs算法。。。

#include<bits/stdc++.h>
using namespace std;
vector<int>G[110],tp;
int c[110],n;
inline bool dfs(int x)
{
	c[x]=-1;
	for(int y:G[x])
	{
		if(c[y]<0)return 0;//有环
		if(!c[y]&&!dfs(y))return 0;//图走不完(孩子有环)
	}
	c[x]=1;tp.push_back(x);//满足条件,压入
	return 1;
}
inline bool check()
{
	for(int i=1;i<=n;i++)if(!c[i]&&!dfs(i))return 0;//判断每一个点
	reverse(tp.begin(),tp.end());//记录时为逆着记录,翻转过来
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)
	{
		while(scanf("%d",&x)&&x)G[i].push_back(x);
	}
	if(check())for(int x:tp)printf("%d ",x);
	else puts("-1");
	return 0;
}