本文主要是介绍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--拓扑排序//两种解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
