D01 拓扑排序

Kahn算法 O(n):

// Kahn算法 O(n)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,m;
vector<int> G[N],tp;
int din[N];

bool toposort()
{
	tp.clear();
	queue<int> q; for (int i=1;i<=n;i++)if(din[i] == 0)q.push(i);
	while(q.size())
	{
		int x=q.front();q.pop();
		tp.push_back(x);
		for(auto y:G[x])
		{
			din[y]--;
			if(din[y]==0)q.push(y);//如果y的入度变为0，则将y加入队列
		}
	}
	return tp.size()==n;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++) G[i].clear();
		memset(din, 0, sizeof(din));
		for(int i=1,x,y;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			G[x].push_back(y);
			din[y]++;
		}
		
		if (!toposort()) puts("-1");
		else { for(auto x:tp)printf("%d ", x); printf("\n"); }
	}
	return 0;
}

DFS算法 O(n):

// DFS算法 O(n)
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
vector<int> G[N], tp;
int c[N]; // 染色数组

bool dfs(int x)
{
	c[x] = -1;
	for (int y : G[x])
	{
		if (c[y] < 0)
			return 0; // 有环
		else if (!c[y])
			if (!dfs(y))
				return 0;
	}
	c[x] = 1;
	tp.push_back(x);
	return 1;
}
bool toposort()
{
	tp.clear();
	memset(c, 0, sizeof(c));
	for (int x = 1; x <= n; x++)if (!c[x])
			if (!dfs(x))
				return 0;
	reverse(tp.begin(), tp.end());
	return 1;
}
int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= n; i++)G[i].clear();
		for (int i =1,x,y; i <=m; i++)
		{
			scanf("%d%d", &x, &y);
			G[x].push_back(y);
		}
		if (!toposort())puts("-1");
		else {for (int x : tp)printf("%d ", x);printf("\n");}
	}
	return 0;
}