并查集入门题。

数组结构code1：

#include
     
      #define maxn 1005#define max(a,b) a>b?a:b#define min(a,b) a
      
       <= n;i ++){        set[i] = i;        ifhas[i] = 0;    }}void Merge(int a,int b){    int big,small;    big = max(set[a],set[b]);    small= min(set[a],set[b]);    for(int i = 1;i <= n;i ++)    {        if(set[i] == big){            set[i] = small;        }    }}int main(void){    while(cin >> n && n!=0)    {        init();        cin >> m;        int i,j;        for(i = 0;i < m;i ++){            cin >> s >> e;            Merge(s,e);        }        int ans = 0;        for(int i = 1;i <= n;i ++)        {            if(ifhas[set[i]] == 0){                ans ++;                ifhas[set[i]] = 1;            }        }        cout << ans - 1 << endl;    }    return 0;}
      
     

 树结构code2

#include 
     
      #include 
      
       #define maxn 1005using namespace std;int set[maxn];void init(int n){    int i;    for(i = 1;i <=n;i ++)    {        set[i] = i;    }}int find(int x){    int fa = x;    while(fa != set[fa])        fa = set[fa];    return fa;}void merge(int a,int b){    int fa,fb;    fa = find(a);    fb = find(b);    set[fb] = fa;}int main(){    int n,m,a,b;        while(cin >> n && n!= 0)    {        init(n);        cin >> m;        for(int i = 1;i <= m;i ++){            cin >> a >> b;            merge(a,b);        }        for(int i = 1;i <= n;i ++){            set[i] = find(i);            //cout << "set[" << i << "]=" << set[i] << endl;        }        int ans = 0;        for(int i = 1;i <= n;i ++)        {            if(set[i] == i){                ans ++;            }        }        cout << ans - 1 << endl;    }    return 0;}
      
     

树结构（优化，深度小的移到深度大的）

#include 
     
      #include 
      
       #define maxn 1005using namespace std;int set[maxn];int height[maxn];void init(int n){    int i;    for(i = 1;i <=n;i ++)    {        set[i] = i;        height[i] = 1;    }}int find(int x){    int fa = x;    while(fa != set[fa])        fa = set[fa];    return fa;}void merge(int a,int b){    int fa,fb;    fa = find(a);    fb = find(b);    if(height[fa] > height[fb]){        set[fb] = fa;    }    else if(height[fb] > height[fa]){        set[fa] = fb;    }    else{        set[fb] = fa;        height[fa] ++;    }}int main(){    int n,m,a,b;        while(cin >> n && n!= 0)    {        init(n);        cin >> m;        for(int i = 1;i <= m;i ++){            cin >> a >> b;            merge(a,b);        }        for(int i = 1;i <= n;i ++){            set[i] = find(i);            //cout << "set[" << i << "]=" << set[i] << endl;        }        int ans = 0;        for(int i = 1;i <= n;i ++)        {            if(set[i] == i){                ans ++;            }        }        cout << ans - 1 << endl;    }    return 0;}
      
     

树结构（优化，深度小的移到深度大的 + 路径压缩）

#include 
     
      #include 
      
       #define maxn 1005using namespace std;int set[maxn];int height[maxn];void init(int n){    int i;    for(i = 1;i <=n;i ++)    {        set[i] = i;        height[i] = 1;    }}int find(int x){    int fa = x;    int j,i;    while(fa != set[fa])        fa = set[fa];    i = x;    while(i != fa)    {        j = set[i];        set[j] = fa;        i = j;    }    return fa;}void merge(int a,int b){    int fa,fb;    fa = find(a);    fb = find(b);    if(height[fa] > height[fb]){        set[fb] = fa;    }    else if(height[fb] > height[fa]){        set[fa] = fb;    }    else{        set[fb] = fa;        height[fa] ++;    }}int main(){    int n,m,a,b;        while(cin >> n && n!= 0)    {        init(n);        cin >> m;        for(int i = 1;i <= m;i ++){            cin >> a >> b;            merge(a,b);        }        for(int i = 1;i <= n;i ++){            set[i] = find(i);            //cout << "set[" << i << "]=" << set[i] << endl;        }        int ans = 0;        for(int i = 1;i <= n;i ++)        {            if(set[i] == i){                ans ++;            }        }        cout << ans - 1 << endl;    }    return 0;}