L2-024 部落 (25分)【并查集】

待我称王封你为后i 2022-11-19 12:38 189阅读 0赞

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

**输入格式：**  
输入在第一行给出一个正整数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

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

**这道题考察了并查集。并查集的模板主要包括四个部分：初始化，寻找根节点，合并，求连通分量个数。（强烈推荐一篇文章，解释并查集非常形象易懂，[链接][Link 1]）**

**1、初始化**

void init() {
        
    	for(int i = 1; i <= 10005; i++) {
        
    		father[i] = i;
    	}
    }

**2、寻找根节点**  
**一般写法**

int find(int x) {
        
    	if(father[x] == x) return x;
    	return find(father[x]);
    }

**优化写法（路径压缩）**

int find(int x) {
        
    	if(father[x] == x) return x;
    	return father[x] = find(father[x]);
    }

**3、合并集合**

void merge(int x, int y) {
        
    	int fx = find(x), fy = find(y);
    	if(fx != fy) father[fx] = fy;
    }

**4、求连通分量个数**

int count() {
        
    	int cnt = 0;
    	for(int i = 0; i < n; i++) {
        
    		if(father[i] == i) cnt++;
    	}
    	return cnt;
    }

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

**father数组来存储该节点的上一个节点。因为社区总人数即为编号个数，所以将他们存储到set中，最后元素个数即为总人数；不相交部落个数可以寻找有几个根节点，根节点个数即为不相交部落个数；判断两个人是否属于同一个部落，可以寻找各自的根节点，如果根节点相同则为同一部落，否则不同。**

代码有参考[链接][Link 2]

#include <iostream>
    #include <set>
    using namespace std;
    
    int father[10005];
    void init() {
        
    	for(int i = 1; i <= 10005; i++) {
        
    		father[i] = i;
    	}
    }
    int find(int x) {
        
    	if(father[x] == x) return x;
    	return father[x] = find(father[x]);
    }
    void merge(int x, int y) {
        
    	int fx = find(x), fy = find(y);
    	if(fx != fy) father[fx] = fy;
    }
    int main() {
        
    	int n;
    	cin >> n;
    	init();
    	set<int> st;
    	for(int i = 0; i < n; i++) {
        
    		int k, tmp;
    		cin >> k >> tmp;
    		st.insert(tmp);
    		for(int j = 1; j < k; j++) {
        
    			int id;
    			cin >> id;
    			st.insert(id);
    			merge(tmp, id);
    		}
    	}
    	set<int> cnt;
    	for(int i = 1; i <= st.size(); i++) {
        
    		int t = find(i);
    		cnt.insert(t);
    	}
    	printf("%d %d\n", st.size(), cnt.size());
    	int q;
    	cin >> q;
    	while(q--) {
        
    		int a, b;
    		cin >> a >> b;
    		int fa = find(a), fb = find(b);
    		if(fa == fb) cout << "Y\n";
    		else cout << "N\n";
    	}
    }

[Link 1]: https://blog.csdn.net/the_ZED/article/details/105126583?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.control
[Link 2]: https://blog.csdn.net/weixin_45845039/article/details/109643390?ops_request_misc=%25257B%252522request%25255Fid%252522%25253A%252522161054156416780258088275%252522%25252C%252522scm%252522%25253A%25252220140713.130102334.pc%25255Fblog.%252522%25257D&request_id=161054156416780258088275&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v1~rank_blog_v1-1-109643390.pc_v1_rank_blog_v1&utm_term=%E9%83%A8%E8%90%BD