> int GetRoot(int x){
>   if(colorset[x] < 0) return x;
>   else return GetRoot(colorset[x]);
> }
> 
> void Union (int a, int b){
>   int rootA = GetRoot(a);
>   int rootB = GetRoot(b);
>  
>   if(rootA == rootB) return;
> 
>   if(colorset[rootA] <= colorset[rootB]){
>  
>     colorset[rootA] += colorset[rootB];
>     colorset[rootB] = rootA;
> 
>     if(colorset[rootA] == -1*setsize){
>       printf("Possible\n");
>       exit(0);
>     }
>   } else {
>     colorset[rootB] += colorset[rootA];
>     colorset[rootA] = rootB;
> 
>     if(colorset[rootB] == -1*setsize){
>       printf("Possible\n");
>       exit(0);
>     }
>   }
> }

• 其实就是防止出现退化的树，所以合并的时候，根据每部分的节点数来选择新的根 (0) sunmoonstar_love 2005-07-28 22:09:16
  • 你这个并查集不能通用的吧 (0) frkstyc 2005-07-28 22:11:46
    • 这样可以了，只要把colorset[]换成你想要的 (435) sunmoonstar_love 2005-07-28 22:20:29
      • 假如存在多个同样大小的集合的话你这个模型根本就没法分辨 (483) frkstyc 2005-07-28 22:21:57
        • 难道这道题，在合并过程中不会出现大小相等的集合么？ (0) sunmoonstar_love 2005-07-28 22:32:02
          • ft....被你的变量名误导了…… (0) frkstyc 2005-07-28 22:34:07
            • sorry (0) sunmoonstar_love 2005-07-28 22:35:37
              • 是我看错了…… (0) frkstyc 2005-07-28 22:36:49
      • 为什么？？那不是小于等于么？？？ (483) sunmoonstar_love 2005-07-28 22:24:56
        • 找一个题目写写就知道了 (0) frkstyc 2005-07-28 22:29:06
          • 先教教我，怎么做压缩，谢谢了 (0) sunmoonstar_love 2005-07-28 22:32:58
            • find的时候把路上的节点全部直接接到根上 (0) frkstyc 2005-07-28 22:34:41