洛谷：P1536：村村通

题目

P1536：村村通

分析

这一题可以在P1551：亲戚基础上进行。初始化、查找、合并等代码是一样的。但需要多一个函数来统计独立集合的个数——也就是相互间不存在“亲戚”关系的集合最终有几个，这个数字减1就是还要建立连通关系的数量。

两个并查集，如果能找到两个不同的最终父辈，那一定是两个独立的集合。而一个并查集的特征是有且只有一个元素，它的“父辈”是自己——这是由合并成并查集的过程决定的。想通了这一点，代码就简单了：

int countSets(int n)
{
    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (parents[i] == i)
        {
            count++;
        }
    }
    return count;
}

答案

思考

本题在前一题的基础上，可以很快完成。