AcWing 837. 连通块中点的数量
原题链接
中等
给定一个包含 n 个点(编号为 1∼n)的无向图,初始时图中没有边。
现在要进行 m 个操作,操作共有三种:
C a b,在点 a 和点 b 之间连一条边,a 和 b 可能相等;
Q1 a b,询问点 a 和点 b 是否在同一个连通块中,a 和 b 可能相等;
Q2 a,询问点 a 所在连通块中点的数量;
输入格式
第一行输入整数 n 和 m。
接下来 m 行,每行包含一个操作指令,指令为 C a b,Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b,如果 a 和 b 在同一个连通块中,则输出 Yes,否则输出 No。
对于每个询问指令 Q2 a,输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤105
输入样例:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例:
Yes
2
3
blablabla
#### 时间复杂度O(1)
#### 参考文献
#include<iostream>
using namespace std;
const int N=100010;
int p[N],cot[N];
int n,m;
int find(int x) //返回祖宗节点,可以把find'直接认为father 本质上:是将其路径压缩了,把a→b→c→d变为a→d b→d c→d;是通过递归实现
{
if(p[x]!=x) //若不是祖宗节点
p[x]=find(p[x]);//父节点指向父节点的祖宗节点 举个栗子:a的父节点为b的祖宗节点(d变为a) 同理类推
return p[x];//返回(祖宗节点)该元素最终父节点。
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
p[i]=i,cot[i]=1;//把每个节点的祖宗节点定义为本身,也可以说:它的父节点是他本身。再用cot(初始都为1)数组去记录祖宗节点下有多少个子节点
while(m--)
{
int a,b;
string op;
cin>>op;
if(op=="C")//建边的操作:在A————B建一条边我们是不是可以看成B是A儿子节点.分两种情况来讨论;
{
cin>>a>>b;
if(find(a)==find(b)) //first:本来有边我总不可能再去建一条把:我们实现的操作:直接continue结束本次循环。
continue;
cot[find(b)]=cot[find(a)]+cot[find(b)]; //second:压缩路径+根节点直接操作为实现O(1)的操作~~否则的话我们得去统计该集合有多少个节点
// 思考一下暴力:得去遍历这样一个p去找有多少个节点。
p[find(a)]=find(b);//a的父节点变为b,把a这颗树接到b上
}
else if(op=="Q1")
{
cin>>a>>b;
if(find(a)==find(b))//两个祖宗节点都一样肯定在一棵树: 举个栗子:你们的祖宗都是一个人肯定是亲人
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
else
{
cin>>a;
cout<<cot[find(a)]<<endl;//think:只对根节点操作看看up 在加的时候都是直接对cot[find(x)]操作的。
}
}
return 0;
}
blablabla