团体程序设计天梯赛-练习集 L2-024 部落 (25分) 并查集思想

向右看齐 2023-10-11 15:06 26阅读 0赞

### L2-024 部落 (25分) ###

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

**输入格式：**  
输入在第一行给出一个正整数N（≤10^4 ），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：K P\[1\] P\[2\] ⋯ P\[K\]

其中K是小圈子里的人数，P\[i\]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10^4 。之后一行给出一个非负整数Q（≤10^4 ），是查询次数。随后Q行，每行给出一对被查询的人的编号。

**输出格式：**  
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

**输入样例：**

4
    3 10 1 2
    2 3 4
    4 1 5 7 8
    3 9 6 4
    2
    10 5
    3 7

**输出样例：**

10 2
    Y
    N

--------------------

本题思路：两两建立并查集，用 set 存储社区的总人数，每次建立一个连通关系，记录次数加一，那么总人数减去记录的连通个数就是部落的个数。

#include<bits/stdc++.h>
    #define Inf 0x3f3f3f
    const int N = 10005;
    using namespace std;
    int n, k, q;
    int sum;//sum统计并查集连通个数
    int pre[N];
    set<int> se;
    
    int SearchRoot(int root){
        
    	int t, son;
    	son = root;
    	while(root != pre[root]){
        //查找祖先节点
    		root = pre[root];
    	}
    	while(son != root){
        //路径压缩
    		t = pre[son];
    		pre[son] = root;
    		son = t;
    	}
    	return root;
    }
    void join(int a1, int a2){
        
    	int roota1 = SearchRoot(a1);
    	int roota2 = SearchRoot(a2);
    	if(roota1!=roota2){
        
    		pre[roota1] = pre[roota2];
    		sum++;
    	}
    }
    
    int main(){
        
    	for(int i = 0; i < N; i ++)
    		pre[i] = i;
    	int  a1, a2;
    	cin >> n;
    	while(n--){
        
    		cin >> k;
    		cin >> a1;
    		se.insert(a1);
    		for(int i = 1; i < k; i ++){
        
    			cin >> a2;
    			join(a1, a2);
    			se.insert(a2);
    			a1 = a2;
    		}
    	}
    	cout << se.size() << " " << se.size()-sum << endl;
    	int p1, p2;
    	cin >> q;
    	while(q--){
        
    		cin >> p1 >> p2;
    		int rootp1 = SearchRoot(p1);
    		int rootp2 = SearchRoot(p2);
    		if(rootp1!=rootp2){
        
    			cout << "N" << endl;
    		}else{
        
    			cout << "Y" << endl;
    		}
    	}
    
    	return 0;
    }