FJUT ACM 2144 并查集

并查集

TimeLimit:3000MS MemoryLimit:128MB

64-bit integer IO format:%lld

Problem Description

并查集详解：http://blog.csdn.net/dellaserss/article/details/7724401

这里注意一下，用递归压缩路径的同学，可能会爆栈，从而导致

Runtime Error 建议用循环压缩路径

Input

输入多组数据

每组数据第一行是两个整数n（1<=n<=10^6），m(1<=m<=10^6)。分别表示元素数、操作数（初始时每个元素以自己为一个集合,元素编号是1-n）

接下来m行，每行有如下几种输入：

union x y ——表示将x所在的集合和y所在的集合合并为一个集合。

same x y ——询问x和y是否为同一个集合、为同一个集合输出1，不同集合输出0

num x ——询问x所在的集合共有多少个元素

max x ——询问x所在的集合中元素编号最大是多少

setnum ——询问现在总共有多少个集合

Output

对于每个same、num、max、setnum操作输出一行，用一个整数表示答案。

SampleInput

5 10
setnum
same 1 2
union 1 2
same 1 2
union 2 3
same 1 3
union 4 5
setnum
max 1
num 4

SampleOutput

5
0
1
1
2
3
2
[思路]：因为这是一题并差集进行多种操作得到题目，期间涉及连接集合，查询集合最大值，查询集合元素，输出现在有几个集合的操作
，我的一开始的思路是建立一个并查集，在连接过程进行压缩路径，防止并查集退化至o（n），而压缩路径就是把多个子节点连接到一个父
节点上，
如图：

然后我一开始的思路在寻找集合的元素最大值，与寻找元素的个数，进行了2次O（n）的查询，结果是TLE，然后看了数据后，最坏的情况有10的6次方个元素，

进行10的6次方次查询，那o（n）的复杂度必定TLE，经过CWL学长的提醒，必须用o(1)的查询，不然是无法通过的

于是我改了下思路，在连接时，将集合的最大值连接为父节点，这样的话，每次查询只要查询集合的代表元素，即集合的父节点（最大值），

就可以了，进行O（1）的查询

而元素的值，我用了数组来做，有点类似前缀和+数组标记的思想，就是先把数组内的元素所对应的值置为1，再进行累加操作，因为每个节点的连接，

必然把每个节点所代表的集合的元素相加，就可以得到结果！

要注意一点：再进行元素集合个数的查询的时侯，要注意数据有很恶心的，就是把同个集合的元素进行连接，这样很容易导致错误。

还有注意点：不要使用cin,因为太慢了，同样的算法，cin actime:1000ms+ ;scanf actime:300ms+;

贴上代码的核心：

  1 /**
  2 rid: 157411
  3 user: 136155330
  4 time: 2018-02-03 17:46:19
  5 result: Accepted 
  6 */
  7 #include<stdio.h>
  8 #include<string.h>
  9 #define MAXN 1000005
 10 int pre[MAXN];///这个是并差集的指向
 11 int flags[MAXN];///求和
 12 int unionsearch(int root)
 13 {
 14     int son,tmp;
 15     son=root;
 16     while(root!=pre[root])///寻找父节点，一层一层向上
 17     {
 18      root=pre[root];
 19     }
 20     while(root!=son)///路径压缩，就是先将原上级保持在tmp内，在把pre[son]指向父节点，然后再将tmp赋值给son
 21     {tmp=pre[son];
 22     pre[son]=root;///这个过程会不断的去压缩路径，来优化，防止算法退化为O(N)的查找
 23     son=tmp;
 24     }///其实可以以递归写
 25     /**
 26     来至CWL学长的代码：
 27     int acfind(int x)
 28     {
 29     return pre[x]==x?x:pre[x]=acfind(pre[x]);
 30     }
 31     **/
 32     return root;
 33 }
 34 int unionnum(int x)
 35 {
 36     printf("%d
",flags[unionsearch(x)]);
 37 }///通过unionsearch查找最大值的父节点，然后输出标记值
 38 int unionmax(int x)
 39 {
 40     unionsearch(x);
 41     printf("%d
",pre[x]);
 42 }///unionsearch(x):主要是压缩路径，保证路径连接最大值，因为我的max值是在父节点
 43 int unionjoin(int x,int y)
 44 {
 45 int a;
 46 int b;
 47 a=unionsearch(x);
 48 b=unionsearch(y);///任何两个数去链接，得到的必然是大的值为父节点
 49 if(a!=b)
 50     {
 51         if(a>b)
 52             {pre[b]=a;
 53             flags[a]+=flags[b];
 54             }
 55         else if(a<b)
 56             {pre[a]=b;
 57             flags[b]+=flags[a];
 58             }///把最大值放到父节点去。因为每次进行连接，都会去选择最大值的节点进行连接
 59     }///因为flags初始化为1，只要每次连接都累加就可以，得到数字的和
 60 }