并查集

 

百科名片

并查集

在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。

 

目录

展开

 

 

定义

　　并查集是一种树型的 ，用于处理一些不相交 （Disjoint Sets）的合并及查询问题。常常在使用中以 来表示。
 
　　集就是让每个元素构成一个单元素的集合，并就是按一定顺序将属于同一组的元素所在的集合合并。
 

主要操作

初始化

　　把每个点所在集合初始化为其自身。
 
　　通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。

查找

　　查找元素所在的集合，即根节点。

合并

　　将两个元素所在的集合合并为一个集合。
 
　　通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

#include <stdio.h>

int set[101000];

int num[101000];
int maxn = 1;

void make_set(  )

{
  for( int i = 1; i <= 100000; i++)
  {
     set[i] = i;
     num[i] = 1;
  }
}

int find( int x)

{
  /*
  if( x != set[x] )
      set[x] = find(set[x]);
  return set[x];
  */
  return x == set[x] ? set[x] : set[x] = find(set[x]);
 
}

void merge( int x, int y)

{
   int x1 = find(x);
   int y1 = find(y);
   if( x1 != y1)
   {
      set[x1] = y1;
      num[y1] += num[x1];
   maxn = maxn > num[y1] ? maxn : num[y1];   
   }
}

int main( )

{
 int N, a, b;
 while( scanf("%d",&N)!= EOF )
 {
   maxn = 1;
   make_set( );
   for( int i = 1; i <= N; i++)
   {
   scanf("%d%d",&a,&b);
   merge(a,b);
   }
   printf("%d\n",maxn);   
 } 
 return 0;
}