HDU 1272 小希的迷宮 並查集

1、判斷是不是只有一個連通量。

2、判斷有沒有環

代碼如下：

[cpp] 
#include <iostream>  
#include <vector>  
#include <list>  
#include <deque>  
#include <queue>  
#include <iterator>  
#include <stack>  
#include <map>  
#include <set>  
#include <algorithm>  
#include <cctype>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <string>  
#include <cmath>  
using namespace std; 
 
const int N=100011; 
typedef long long LL; 
 
int parent[N],flag; 
bool vis[N]; 
 
void build() 
{ 
    for(int i=0;i<N;i++) 
        parent[i]=i; 
} 
 
int find(int x) 
{ 
    int r = x; 
    while (parent[r] != r)   //循環結束，則找到根節點  
          r = parent[r]; 
    int i = x; 
    while (i != r) //本循環修改查找路徑中所有節點  
    { 
         int j = parent[i]; 
         parent[i] = r; 
         i = j; 
    } 
    return r; 
} 
 
void uniou(int x,int y) 
{ 
    x=find(x); 
    y=find(y); 
    if(x==y) 
        flag=1; 
    else 
        parent[x]=y; 
} 
 
void liantong() 
{ 
    int i,sum=0; 
    for(i=1;i<N;i++) 
    { 
        if(!vis[i]&&parent[i]==i)//i存在，且parent[i]==i，一個連通  
            sum++; 
        if(sum>1) 
        { 
            flag=1;break; 
        } 
    } 
} 
 
int main() 
{ 
    int i,j,a,b; 
    while(scanf("%d%d",&a,&b)) 
    { 
        if(a==-1&&b==-1)    break; 
        if(a==0&&b==0) 
        { 
            printf("Yes\n"); 
            continue; 
        } 
        memset(vis,true,sizeof(vis)); 
        build(); 
        flag=0; 
        uniou(a,b); 
        vis[a]=vis[b]=false; 
        while(scanf("%d%d",&a,&b)) 
        { 
            if(a==0&&b==0)  break; 
            uniou(a,b); 
            vis[a]=vis[b]=false; 
        } 
        liantong(); 
        if(flag==0) 
            printf("Yes\n"); 
        else 
            printf("No\n"); 
    } 
 
    return 0; 
}