判断一颗树是否有环

发表于 | 分类于
判断一个树是否有环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int flag=1;
int v[100];
int head[100],ver[100<<1],nex[100<<1];
int tot;
void add(int x,int y){
	ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}
bool dfs(int now,int fa){
    // printf("now=%d\n",now);
    v[now]=1;
    for(int i=head[now];i;i=nex[i]){
        int y=ver[i];
        // printf("y=%d\n",y);
        // printf("%d %d\n",now,y);
        if(y==fa) continue;
        else {
            // printf("%d %d\n",now,y);
            if(v[y]) return 1;
            if(dfs(y,now)) return 1;
        }
    }
    return 0;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    if(dfs(1,0)) printf("you\n");
    else printf("wu\n");
    for(int i=1;i<=n;i++) printf("%d",v[i]);
    //system("pause");
}