UVa - 10305 - Ordering Tasks(拓扑排序DFS)

拓扑排序DFS模版

bool dfs(int u){vis[u]=-1;// 访问标志，//-1正在访问 1访问完成 0没有访问 for(int v=1 ;v<=n ;v++){if(G[u][v]){//存在环路 if(vis[v]<0)return false;if(!vis[v]&&!dfs(v))return false;}}vis[u] = 1;topo[--t]=u;return true;
}bool toposort(){t=n;for(int u=1;u<=n;u++){if(!vis[u]){if(!dfs(u))return false;		}}return true;
}

#include<iostream>
#include<cstring>
using namespace std;
int n,m,x,y,t;
int G[105][105];
int vis[105];
int topo[105];
bool dfs(int u){vis[u] = -1;for(int v=1 ;v<=n ;v++){if(G[u][v]){if(vis[v]<0)return false;if(!vis[v]&&!dfs(v)) return false;}}vis[u]=1;topo[--t] = u;return true;
}
bool toposort(){t=n;for(int u=1 ;u<=n ;u++){if(!vis[u]){if(!dfs(u))return false;}}return true;
}int main(){
//	freopen("input.txt","r",stdin);while(cin>>n>>m){if(n==m&&n==0)break;memset(G,0,sizeof(G));memset(vis,0,sizeof(vis));for(int i=0 ;i<m ;i++){cin>>x>>y;G[x][y] = 1;}if(toposort()){cout<<topo[0];for(int i=1 ;i<n ;i++){cout<<" "<<topo[i];}cout<<endl;}}return 0;
}