HDU 1232 畅通工程

题目解析

基础的并查集问题

代码

1.没有路径压缩的

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define MIN(a,b) (a
      
       b a:b) #define Swap(a,b) {(a)=(a)^(b); (b)=(a)^(b); (a)=(a)^(b);} #define MAXN 65535 #define INF 1e9 int city[1005]; int find(int x){ //不存在路径压缩 int r=x; while(city[r] != r) r = city[r]; return r; } int main() { int n,m; int i,j; int a,b; int count; while(scanf(%d, &n), n){ scanf(%d, &m); for(i=1; i<=n; i++) //初始化父亲数组 city[i] = i; for(i=0;i
       
        
 
        
2.有路径压缩的
        
 
        
#include 
         
          
#include 
          
            #include 
           
             #include 
            
              #define MIN(a,b) (a
             
              b a:b) #define Swap(a,b) {(a)=(a)^(b); (b)=(a)^(b); (a)=(a)^(b);} #define MAXN 65535 #define INF 1e9 int fa[1005]; int find(int x){ //存在路径压缩 if(fa[x]!=x) fa[x] = find(fa[x]); return fa[x]; } int main(){ int m, n; int x,y,fx,fy; int i, count; while(scanf(%d, &n), n){ scanf(%d, &m); for(i = 1; i<=n; i++) //初始化父亲数组 fa[i] = i; for(i = 0; i