【题目描述】
已经深夜了，露子仍然在公园里仰望星空。你走近后，她对你说：“呜—，你看夜空中的星星。它们本来都是孤独地毫无联系，但人们赋予了它们各种地联想，在它们之间连上了线，便形成了夜空中无数的星座。”你回答：“是啊。为什么我们不自己创造一个美丽的星空呢？”
假设夜空中一共有n颗星星，它们初始时都没有连线。接下来，露子会给你m条指令。一共有以下三种指令：
1.在某两颗星星间连线。（可能会重复连接两颗星星）
2.询问你当前夜空中一共有多少个星座。
3.某两颗星星当前是否属于同一个星座。
其中星座是指：至少由两颗星星组成的，连通的一群星星。
现在就请你实现露子的愿望吧。
【输入格式】
第一行包含两个整数n和m，分别表示星星总数和指令条数。
接下来有m行，每一行的形式是以下三种之一：
1.“a x y”（不包含引号），表示连接编号为x和y的星星(1<=x,y<=n, x!=y)。
2.“b”（不包含引号），表示询问当前夜空中一共有多少个星座。
3.“c x y”，表示询问x和y当前是否属于同一个星座(1<=x,y<=n, x!=y)。
【输出格式】
按指令给出的顺序回答，每个回答各占一行。
对于每一条b类指令，输出一个整数表示当前夜空中有多少个星座。
对于每一条c类指令，输出一行YES或者NO。YES代表这两颗星星是同一个星座的，NO代表他们不是同一个星座的。
【样例输入】
4 10
b
c 1 2
a 1 2
b
a 3 4
b
c 1 3
a 2 3
b
c 1 3
【样例输出】
0
NO
1
2
NO
1
YES
【数据规模】
对于30%的数据，n<=100, m<=100。
对于100%的数据，n<=100000, m<=100000。
时间限制：1s。
【提示】
使用并查集。
并查集已经熟悉了,数据规模比较大的时候,这里多了几个细节.
1. 一定用scanf,比较麻烦的是每一行还会有一个换行符的处理
2. 路径压缩很必要 这样可以减少find中的循环次数
3. 按Rank合并(深度) 每次join的时候把 较浅的集合 加到 较深的集合里 // 维护深度只在合并两个同等深度的树时才增加1
4. 计算星座个数时的在线处理 根据合并的两个数当时的孤立状态而决定
PS:不知道是不是哪里写错了还是因为数据点的特性 加了按Rank合并的部分，反而慢了100ms左右（不是偶然现象，经过大量测试）。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
//这里的独立块也就是星座 指的是 大于等于2的才行
bool iso[100010]={0};
int preNode[100010];//记录i的上级
int Rank[100010]={0}; //记录某星座的深度
int n,m;
int groupCount = 0;
int find(int x){ //找到x的根节点
int root = x;
while(root != preNode[root]){
root = preNode[root];
}
//压缩路径 减少查询次数
while(x != root) {
int tmp = preNode[x];
preNode[x] = root;
x = tmp;
}
return root;
}
//尽量把小的星座加入到较大的星座里
void join(int x , int y){
int root_x = find(x);
int root_y = find(y);
if(root_x == root_y)//如果是同一个星座的 没必要继续了
return;
//0表示都不是孤立点 1表示有一个是孤立点 2表示两个都是孤立点
int tmp = iso[x]+iso[y];
if(tmp==0)
groupCount--;
else if(tmp==2)
groupCount++;
//preNode[root_y] = root_x;
//把较浅的集合并到较深的集合里
if(Rank[root_x] > Rank[root_y]){//root_x的深度更深 所以把y加到它里面
preNode[root_y] = root_x; //Rank不变
} else {
preNode[root_x] = root_y;
if(Rank[root_x] == Rank[root_y])
Rank[root_y]++;//加了一层
}
}
// inline int getGroupCount(){
// int num = 0;
// for (int i = 1; i <= n; ++i)
// if(!iso[i] and preNode[i]==i)//不是孤立的且是根节点
// num++;
// return num;
// }
int main(int argc, char const *argv[])
{
scanf("%d %d",&n,&m);
getchar();//获取每行的结束符
for (int i = 1; i <= n; ++i){
preNode[i]=i;
iso[i] = true;
}
int cur = 0;
while(1)
{
//cout<<cur<<endl;
if(cur==m)
break;
char flag;
scanf("%c",&flag);
if(flag == '
')
continue;
if(flag == EOF)
break;
int a,b;
cur++;
switch(flag){
case 'a':
scanf("%d %d",&a,&b);
join(a,b);
//连接过肯定不是孤立的
iso[a] = false;
iso[b] = false;
break;
case 'b':
printf("%d
",groupCount);
break;
case 'c':
scanf("%d %d",&a,&b);
if(find(a)==find(b))
printf("YES
");
else
printf("NO
");
break;
}
getchar();//获取每行的结束符
}
return 0;
}
/*
星座数量的更新:
主要是在join的时候
如果两个点都是孤立点 则 星座数量加1
如果其中一个是孤立点 则 星座数理不变
如果两个都不是孤立点 则 星座数理减1
*/