连通块中点的数量

给定一个包含 nn 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

现在要进行 mm 个 *** 作， *** 作共有三种：

1. C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
2. Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
3. Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个 *** 作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 aa 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

 (并查集变形题，多维护了size数组，就是每个祖宗节点有多少子孙)

C++

#include
using namespace std;
const int N = 1e5+10;
int p[N],s[N];
int find(int x)
{
	if(p[x]!=x) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	    p[i] = i;
	    s[i] = 1;
	}
	while(m--){
		string str;
		int a,b;
		cin>>str;
		if(str=="C"){
			cin>>a>>b;
			if(find(a)!=find(b)){
				s[find(b)]+=s[find(a)];//注意这两个语句千万不能调换
			    p[find(a)] = find(b);   
			}
		}
		else if(str=="Q1"){
			cin>>a>>b;
			if(find(a)==find(b)) cout<<"Yes"<>a;
			cout< 
python
 
N = 100001
p = [0] * N
size = [0] * N
def find(x):
    global p
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]
def main():
    global p, size
    n, m = list(map(int, input().split(" ")))
    for i in range(n+1):
        p[i] = i
        size[i] = 1
    for i in range(m):
        st = list(input().split(" "))
        s = st[0]
        if s == 'C':
            a = int(st[1])
            b = int(st[2])
            if find(a) == find(b):
                continue
            size[find(b)] += size[find(a)]
            p[find(a)] = find(b)
        elif s == 'Q1':
            a = int(st[1])
            b = int(st[2])
            if find(a) == find(b):
                print("Yes")
            else:
                print("No")
        else:
            a = int(st[1])
            print(size[find(a)])
main()
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5580949.html