O(1) 的小樂

之前這個問題用深度優先搜索做的。。耗時很長，很顯然這是一個并查集的題目：

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> a[50001];
int n,m,col;
bool v[50001];
void dfs(int k)
{
    int i,j;
    v[k]=1;
    for(i=0;i<a[k].size();i++)
        if(v[a[k][i]]==0)dfs(a[k][i]);
}    
int main()
{
    int i,j,p,q,cn=0;
    while(scanf("%d %d",&n,&m),n||m)
    {
        for(i=1;i<=n;i++)a[i].clear(),v[i]=0;
        for(i=0;i<m;i++)scanf("%d %d",&p,&q),a[p].push_back(q),a[q].push_back(p);
        col=0;
        for(i=1;i<=n;i++)if(v[i]==0)dfs(i),col++;
        printf("Case %d: %d\n",++cn,col);    
    }    
    return 0;
}    

并查集版本：

#include <iostream>
using namespace std;

#define MAXN 500001
struct
{
     int parent;
     int rank;
}UFS[MAXN];          //UnionFindSet   UFS

//其中Parent為正數時表示該節點的父節點下標，為負數時表示該節點為一個根節點，其絕對值為該集合包含的節點總數。
//rank表示權值，在不同問題中有不同的含義。

void MakeSet(int N)     /* 初始化 */
{
     int i;

     for(i=0;i<=N;i++)      //額外增加一位，從0開始可以從1開始也可以
     {
         UFS[i].parent=-1;  /* 開始每個節點單獨構成一個集合 */
         UFS[i].rank=0;     /* 權值視具體情況付初值 */
     }
}

int Root(int x)     /* 查找包含接點x的集合的根節點 */

{
     int i=x,temp;
     while(UFS[i].parent>0)
         i=UFS[i].parent;

     while(i!=x)     /* 壓縮路徑以提高以后檢索效率 */
     {
         temp=UFS[x].parent;            
         UFS[x].parent=i;               //直接將x的祖先命為根節點
         x=temp;                                 //繼續處理x的原祖先
     }
     return i;
}

void Union1(int a,int b)     /* 合并a和b所在的集合 */
{
     int fa,fb;
     fa=Root(a);
     fb=Root(b);
     if(fa==fb) return;

     if(UFS[fa].parent<UFS[fb].parent)     /* 始終將較小樹作為較大樹的子樹 */
     {
         UFS[fa].parent+=UFS[fb].parent;
         UFS[fb].parent=fa;
     }
     else
     {
         UFS[fb].parent+=UFS[fa].parent;
         UFS[fa].parent=fb;
     }
}
void Union2(int a, int b)     //將rank較大的作為父節點
{
    int x = Root(a), y = Root(b);
    if( x == y ) return ;
    if( UFS[x].rank > UFS[y].rank ) UFS[y].parent = x;
    else{
        UFS[x].parent = y;
        if( UFS[x].rank == UFS[y].rank ) UFS[y].rank++;
    }
}

int main()
{
    int N, M, a, b;
    int nCases = 1;
    while(scanf("%d %d", &N, &M) && (M||N))
    {
        MakeSet(N);
        for(int i=1; i<=M; ++i)
        {
            scanf("%d %d", &a, &b);
            a = Root(a);
            b = Root(b);
            //如果a,b不在同一個集合，則合并
            if(a != b)
            {
                N--;
                Union2(a, b);
            }
        }
        printf("Case %d: %d\n", nCases++, N);
    }
    return 0;
}

今天明天總結一下并查集的相關知識吧！