并查集之判断图是否成环—小希的迷宫and is it a tree

两题的核心思想都是判断是否成环,区别在于有向与无向,判断成环的条件就是find(a)=find(b),如果相等就成环,下面贴上AC代码

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 const int N=100005;
 6 int pre[N];
 7 int mark[N];
 8 int flag;
 9 
10 void init()
11 {
12     for(int i=1; i<=N; i++)
13     {
14         mark[i]=0;
15         pre[i]=i;
16     }
17 }
18 int find(int x)
19 {
20     int r=x;
21     while(r!=pre[r])
22         r=pre[r];
23     int i=x,j;
24     while(i!=r)
25     {
26         j=pre[i];
27         pre[i]=r;
28         i=j;
29     }
30     return r;
31 }
32 bool merge(int x,int y)
33 {
34     int fx=find(x);
35     int fy=find(y);
36     if(fx!=fy)
37     {
38         pre[fx]=fy;
39         return true;
40     }
41     else
42     {
43         return false;
44     }
45 }
46 int main()
47 {
48     int a,b;
49     while(~scanf("%d%d",&a,&b)&&(a!=-1&&b!=-1))
50     {
51         init();
52         flag=1;
53         int minn=99999999,maxn=-1;
54         if(a==0&&b==0)
55         {
56             printf("Yes
");
57             continue;
58         }
59         while(a||b)
60         {
61             if(a>maxn)  maxn=a;
62             if(b>maxn)  maxn=b;
63             if(b<minn)  minn=b;
64             if(a<minn)  minn=a;
65             mark[a]=1;
66             mark[b]=1;
67             if(merge(a,b)==false)
68                 flag=0;
69             scanf("%d%d",&a,&b);
70         }
71         if(flag==0)
72             printf("No
");
73         else
74         {
75             int cnt=0;
76             for(int i=minn; i<=maxn; i++)
77                 if(pre[i]==i&&mark[i]==1)
78                     cnt++;
79             if(cnt==1)
80                 printf("Yes
");
81             else
82                 printf("No
");
83         }
84     }
85     return 0;
86 }
原文地址:https://www.cnblogs.com/calmwithdream/p/4925609.html