HDU 5154 Harry and Magical Computer 有向图判环

时间:2022-09-26 05:59:39

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5154

题解:

有向图判环。

1、用dfs,正在访问的节点标记为-1,已经访问过的节点标记为1,没有访问过的节点标记为0,如果访问到-1的节点说明说有环。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL; int n,m; const int maxm=+;
const int maxn=; struct Edge{
int v,ne;
Edge(int v,int ne):v(v),ne(ne){}
Edge(){}
}egs[maxm]; int head[maxn],tot;
int vis[maxn]; void addEdge(int u,int v){
egs[tot]=Edge(v,head[u]);
head[u]=tot++;
} bool dfs(int cur){
vis[cur]=-;
int p=head[cur];
while(p!=-){
Edge &e=egs[p];
if(vis[e.v]==){
if(dfs(e.v)) return true;
}
else if(vis[e.v]==-){
return true;
}
p=e.ne;
}
vis[cur]=;
return false;
} void init(){
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
tot=;
} int main(){
while(scanf("%d%d",&n,&m)==&&n){
init();
while(m--){
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v);
}
int su=;
for(int i=;i<=n;i++){
if(vis[i]==){
if(dfs(i)){
su=; break;
}
}
}
if(su) puts("YES");
else puts("NO");
}
return ;
}

2、拓扑排序。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL; int n, m; const int maxm = + ;
const int maxn = ; struct Edge {
int v, ne;
Edge(int v, int ne) :v(v), ne(ne) {}
Edge() {}
}egs[maxm]; int head[maxn], tot;
int ind[maxn]; void addEdge(int u, int v) {
egs[tot] = Edge(v, head[u]);
head[u] = tot++;
} void init() {
memset(head, -, sizeof(head));
memset(ind, , sizeof(ind));
tot = ;
} int main() {
while (scanf("%d%d", &n, &m) == && n) {
init();
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
ind[v]++;
}
queue<int> q;
for (int i = ; i <= n; i++) {
if (ind[i] == ) q.push(i);
}
while (!q.empty()) {
int u = q.front(); q.pop();
//printf("v:%d\n", v);
int p = head[u];
while (p != -) {
Edge& e = egs[p];
ind[e.v]--;
if (ind[e.v] == ) q.push(e.v);
p = e.ne;
}
}
int su = ;
for (int i = ; i <= n; i++) {
if (ind[i]) { su = ; break; }
}
if (su) puts("YES");
else puts("NO");
}
return ;
}