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;
}

今天明天总结一下并查集的相关知识吧！