kuangbin 专题五：并查集 The Suspects

题目链接：
传送门

1.做法一

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30010;
int parent[N], r[N], n, m, ans;//初始化
void init() {
    memset(parent, -1, sizeof(parent));memset(r, 0, sizeof(r));
}//找到根结点
int findRoot(int x) {
    int xRoot = x;while(parent[xRoot] != -1)xRoot = parent[xRoot];return xRoot;
}//判断是否同组
bool sameGroup(int x, int y) {
    int xRoot = findRoot(x);int yRoot = findRoot(y);return xRoot == yRoot;
}//连接两个结点
void merge(int x, int y) {
    int xRoot = findRoot(x);int yRoot = findRoot(y);if(xRoot != yRoot) {
    if(r[xRoot] > r[yRoot]) {
    parent[yRoot] = xRoot;} else if(r[xRoot] < r[yRoot]) {
    parent[xRoot] = yRoot;} else {
    parent[xRoot] = yRoot;r[yRoot]++;}}
}int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
    if(n == 0 && m == 0) break;//初始化init();//输入每一组for(int i = 0; i < m; i++) {
    int tmp, cur, t;//先读入该组的大小和第一个点scanf("%d%d", &t, &cur);//把第一个点和其他结点连在一起for(int j = 1; j < t; j++) {
    scanf("%d", &tmp);merge(cur, tmp);}}//找到0点的根结点int std = findRoot(0);ans = 0; //遍历看看有多少个和其同根的结点（包括根节点本身）for(int i = 0; i < n; i++){
    int curnum = findRoot(i);if(curnum == std) ans++;}//输出结果printf("%d\n", ans);}return 0;
}

第一种做法就是先记录人数和组数，然后再把每组的第一个人与其他人连接起来，这些都是并查集的基本操作。然后重点在于最后的判断，第一种做法的判断方法是，把0点的根结点找出来，然后遍历所有点，看看有多少点和0点的根结点是相同的。统计完以后输出答案。

2.做法二

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30010;
//amount数组用于存储当前结点的子元素+自己的数量
int parent[N], r[N], amount[N], n, m;//初始化数据
void init() {
    memset(parent, -1, sizeof(parent));memset(r, 0, sizeof(r));//先加上自己for(int i = 0; i < n; i++)amount[i] = 1;
}//找到根结点
int findRoot(int x) {
    int xRoot = x;while(parent[xRoot] != -1)xRoot = parent[xRoot];return xRoot;
}//判断是否同组（这里没用到，我也忘了删）
bool sameGroup(int x, int y) {
    int xRoot = findRoot(x);int yRoot = findRoot(y);return xRoot == yRoot;
}//连接两个结点，同时维护一个数组用于存储当前组的元素数量
void merge(int x, int y) {
    int xRoot = findRoot(x);int yRoot = findRoot(y);if(xRoot != yRoot) {
    if(r[xRoot] > r[yRoot]) {
    parent[yRoot] = xRoot;amount[xRoot] += amount[yRoot];} else if(r[xRoot] < r[yRoot]) {
    parent[xRoot] = yRoot;amount[yRoot] += amount[xRoot];} else {
    parent[xRoot] = yRoot;r[yRoot]++;amount[yRoot] += amount[xRoot];}}
}int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
    //跳出条件if(n == 0 && m == 0) break;//初始化init();//输入各组for(int i = 0; i < m; i++) {
    int tmp, cur, t;//记录下每一组人数，同时记下第一个人scanf("%d%d", &t, &cur);//那第一个人和其他人连接for(int j = 1; j < t; j++) {
    scanf("%d", &tmp);merge(cur, tmp);}}//找到0号的根结点int std = findRoot(0);//输出0的根结点的子元素+自己的数量printf("%d\n", amount[std]);}return 0;
}

这种做法的基本思路与前一种差不多，根本区别在于记录人数的方法。在这种方法中，创建了一个amount数组用于存储其子元素的数量，每次连接时都会处理amount数组，来存下当前点的子结点的数量。因为最终我们要的是其子结点和它本身，所以amount初始化为1。最后找出0的根结点，然后输出amount[std]（std为0的根结点）就好了。