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

• 感觉这只是个优化的unionfind，请讲讲在哪里加压缩 (669) sunmoonstar_love 2005-07-28 22:08:02
• 还能这样实现union-find sets？没见过 (669) frkstyc 2005-07-28 22:08:03
  • 其实就是防止出现退化的树，所以合并的时候，根据每部分的节点数来选择新的根 (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
• 刚才试了一下,根据集合大小合并的优化措施基本上没用 (13) 00448242 2005-07-28 22:40:26
  • 我觉得，也就是防止出现比较差的情况 (17) sunmoonstar_love 2005-07-28 22:41:16
    • 只要路径压缩就够了. (19) 00448242 2005-07-28 22:42:26
    • 我们数据结构老师教我们时，极力推荐这个weight_union()代替simple_union()的，老师研究算法几十年了，不会错吧 (0) sunmoonstar_love 2005-07-28 22:42:58
      • 如果没有路径压缩,这个当然能够起不小的作用,但是加了路径压缩后,这个反而成了累赘. (0) 00448242 2005-07-28 22:44:00
        • 嗯，同意，路径压缩做到getroot()里面么？ (0) sunmoonstar_love 2005-07-28 22:47:51
          • 至少我是这样做的 (0) frkstyc 2005-07-28 22:48:20
  • 你还没碰上那个题，我记得当时去掉了启发式合并就慢了一倍 (17) frkstyc 2005-07-28 22:47:21
    • 哪个题?POJ上没有吗? (0) 00448242 2005-07-28 22:49:53
      • 忘了 (0) frkstyc 2005-07-28 22:50:34
• 看来这个题并查集的好坏对时间并不起多大影响,刚才去了路径压缩,592毫秒 (669) 00448242 2005-07-28 22:47:12
  • 这题并查集不就判个连通么 (0) palmtenor 2005-07-29 17:22:25