hdu-3342-Legal or Not--拓扑排序//两种解法

题目链接：点击：：here~~~

DFS

#include<stdio.h> #include<string.h> int vis[105],map[105][105]; int n,m; bool dfs(int u) {vis[u]=-1;for(int v=0;v<n;v++)if(map[u][v]){if(vis[v]<0) return false;else if(!vis[v]&&!dfs(v)) return false;}vis[u]=1; return true; } bool toposort() {memset(vis,0,sizeof(vis));for(int u=0;u<n;u++)if(!vis[u]){if(!dfs(u)) return false;}return true; } int main() {int u,v;while(scanf("%d%d",&n,&m),n,m){memset(map,0,sizeof(map));for(int i=0;i<m;i++){scanf("%d%d",&u,&v);map[u][v]=1;}if(!toposort()) printf("NO\n");else printf("YES\n");}}
二：

#include<stdio.h> #include<iostream> #include<string.h> #include<vector> using namespace std; vector<int> g[105]; int indu[105],vis[105]; int n,m; void toposort() {int p,flag=0;int k;for(int i=0;i<n;i++){p=0;for(int j=0;j<n;j++){if(indu[j]==0&&!vis[j]){p=1;k=j;vis[k]=1;break;}}if(p!=1){flag=1;break;}for(int r=0;r<g[k].size();r++) indu[g[k][r]]--;}if(flag) printf("NO\n");else printf("YES\n"); } int main() {int u,v;while(scanf("%d%d",&n,&m),n){memset(indu,0,sizeof(indu));memset(vis,0,sizeof(vis));memset(g,0,sizeof(g));for(int i=0;i<m;i++){scanf("%d%d",&u,&v);g[u].push_back(v);indu[v]++;}toposort();} }

总结

以上是生活随笔为你收集整理的hdu-3342-Legal or Not--拓扑排序//两种解法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。