传送门: https://uva.onlinejudge.org/external/103/10305.pdf
拓扑排序(topological sort)简单题
自己代码的思路来自: ==> http://songlee24.github.io/2015/05/07/topological-sorting/
感谢n久前蔡大神扔给我这个链接2333333
#include <bits/stdc++.h>
using namespace std; const int MAXN = ;
bool vis[MAXN];
int G[MAXN][MAXN];
int indegree[MAXN];
int main(){
int n, m;
while(cin >> n >> m){
if(n == && m == ) break;
memset(vis, false, sizeof(vis));
memset(G, , sizeof(G));
memset(indegree, , sizeof(indegree));
for(int i = ; i < m; ++i){
int a, b;
cin >> a >> b;
G[a][b] = ;
indegree[b] += ;
}
queue<int> q;
while(!q.empty()) q.pop();
for(int i = ; i <= n; ++i)
if(!indegree[i]) q.push(i);
int total = n;
while(!q.empty()){
int cur = q.front();
q.pop();
cout << cur;
if(--total) cout << " ";
vis[cur] = true;
for(int i = ; i <= n; ++i){
if(G[cur][i]){
--indegree[i];
if(!indegree[i] && !vis[i])
q.push(i);
}
}
}
cout << endl;
}
return ;
}
入门经典的思路：
#include <bits/stdc++.h>
using namespace std; const int MAXN = ;
int n, m, t;
int vis[MAXN];
int topo[MAXN];
int G[MAXN][MAXN]; bool dfs(int cur){
//vis数组存储三个状态{-1, 0, 1}
//-1 代表该点正在访问中(正在栈帧中)
// 0 代表该点没有被访问过
// 1 代表该点及所有有关系的点都被访问过了
vis[cur] = -;
for(int i = ; i <= n; ++i)
if(G[cur][i]){
//若在访问中遇到符合要求且正在调用的点,证明图存在有向环,不存在拓扑排序
if(vis[i] < ) return false;
else if(!vis[i] && !dfs(i)) return false;
}
vis[cur] = ;
topo[--t] = cur;
return true;
}
bool toposort(){
t = n;
memset(vis, , sizeof(vis));
memset(topo, , sizeof(topo));
for(int i = ; i <= n; ++i)
if(!vis[i])
if(!dfs(i))
return false;
return true;
}
int main(){
while(cin >> n >> m){
if(n == && m == ) break;
memset(G, , sizeof(G));
while(m--){
int a, b;
cin >> a >> b;
G[a][b] = ;
}
if(toposort())
for(int i = ; i < n; ++i) cout << topo[i] << " \n"[i == n-];
}
return ;
}