HDU 3342 Legal or Not(拓扑排序判断成环)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3342

题目大意:n个点,m条有向边,让你判断是否有环。

解题思路:裸题,用dfs版的拓扑排序直接套用即可。

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e2+; int n,m;
int vis[N];
bool G[N][N]; bool dfs(int u){
vis[u]=-;
for(int i=;i<n;i++){
if(G[u][i]){
if(vis[i]==-)
return false;
else if(!vis[i]&&!dfs(i))
return false;
}
}
vis[u]=;
return true;
} bool toposort(){
memset(vis,,sizeof(vis));
for(int i=;i<n;i++){
if(!vis[i]){
if(!dfs(i))
return false;
}
}
return true;
} int main(){
while(~scanf("%d%d",&n,&m)){
memset(G,false,sizeof(G));
if(n==&&m==)
break;
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
G[a][b]=true;
}
if(toposort())
puts("YES");
else
puts("NO");
}
return ;
}
上一篇:HDU 3342 Legal or Not (图是否有环)【拓扑排序】


下一篇:Android 应用程序崩溃日志捕捉