首页 > 代码库 > 拓扑排序

拓扑排序

之前很傻,,感觉看不到拓扑是啥东西。。脑子太烂了吧。。。今晚上瞄了一眼就懂了。。

我就放代码上来就行了。。注释也不打了,,因为太简单了。

#include <iostream>#include <cstring>using namespace std;#define CC(i) memset(i, 0, sizeof(i))const int maxn=105;int g[maxn][maxn], n, m, vis[maxn], top[maxn], cnt;bool dfs(int u) {	vis[u]=-1;	for(int v=1; v<=n; ++v) if(g[u][v]) {		if(vis[v]==-1) return false;		else if(!vis[v] && !dfs(v)) return false;	}	vis[u]=1; top[cnt--]=u;	return true;}bool toposort() {	CC(vis); CC(top); cnt=n;	for(int i=1; i<=n; ++i) if(!vis[i] && !dfs(i)) return false;	return true;}int main() {	int u, v;	cin >> n >> m;	for(int i=1; i<=m; ++i) {		cin >> u >> v;		g[u][v]=1;	}		if(toposort()) {		cout << "Yes\n";		int i;		for(i=1; i<n; ++i) cout << top[i] << " < ";		cout << top[i] << endl;	}	else cout << "No\n";		return 0;}