1013 Battle Over Cities(2)

图的不连通块计数——并查集

题面

见上一篇博客,我相信肯定根本不会有人在乎所以我就不写了。

首先讲一下并查集这个数据结构。

并查集

并查集是一种维护集合(尤其是图中的所有相连点构成的点集)的数据结构,在逻辑上是树型的,其名称中含有“并”(合并两个集合)、“查”(查找自己属于哪个集合)两个要素,说明这种数据结构要支持并和查两个方法。

如果将图中的点以1~n来编号的话,我们可以假设这些点之间存在偏序关系,以便于我们使用树型的逻辑去描述它(这里的树型结构是从下而上的,和一般的自上而下的树不同)。为了减少直接去实现树形结构的开销,又可以用数组去模拟它

因此,定义father[]数组,father[i] = fi 表示点i的父亲节点是fi,放在集合中讲就是i和fi相连通。
特别地,如果对于某点r有 father[r] = r,这就表示节点r是整棵树的根节点(祖宗节点)。如果放在集合中来考虑,可以发现这个r点对于整个集合来说是一个很特殊的点——每个集合一经建立就有且只有一个独一无二的r点,因此理所应当想到可以用r点来代表一个集合。
那么“查找某个点属于哪个集合”任务就等同于“查找某个点的根节点”任务了,由此引出findFather()函数来找根节点,如果两个点所在集合的根节点r相同,那么这两个点必然是相连通的,即:

a与b连通 ⟺ findFather(a)=findFather(b)

int findFather(int node) // 找爹函数
{
    while (node != father[node]) // 如果不是根,就继续找
    {
        node = father[node];
    }
}

此时考虑一种特殊情况,如果这些点如同链表一样排列的话,这个findFather()函数就会在这个链上浪费很多时间(而我们的目标是找到根节点),这里可以用到路径压缩思想,就是在找到根节点的时候顺手把路径上所有点的father[]数组的值改成根节点的值。(这样子再findFather()的话就可以一步跳到根节点去了,注意此时father[]数组的意义已不再是“记录邻接信息”了)

int findFather(int node) // 改进后的找爹函数
{
    // 查
    int cur = node;              // 保存x以便路径压缩
    while (node != father[node]) // 如果不是根,就继续找
    {
        node = father[node];
    }
    while (cur != father[cur]) // 路径压缩
    {
        {
            int temp = cur;
            cur = father[cur];
            father[temp] = cur;
        }
        return node;
    }
}

接下来就是两个集合的合并(Union()函数),如果我们要把a点所在集合A和b点所在集合B合并,很显然我们只要令B的根变成A的根即可(或者反之亦可),即:

使a和b连通 ⟺ 合并A和B ⟺ father[findFather(b)] = findFather(a)

(注意这里不是直接令father[a] = b,这样做相当于是把b从集合B中取出放到A里)

如果我们将“一个集合中所有点对应的father数组都是该集合的根元素”称作“完美压缩”,那么在合并前,如果已经经历过路径压缩,那么A集合和B集合显然都是完美压缩的;而压缩后整个集合并非所有点对应father数组的值都是findFather(a)(原B集合除了根之外的所有点对应的father数组值都是原findFather(b)),即合并后路径并非“完美压缩”。因此即使使用了路径压缩思想,经过若干次查找合并操作的集合仍然不一定是“完美压缩”的。
因此在使a和b连通之前,如果a和b在同一个集合中,并且恰好出现了非“完美压缩”的现象,这时若令father[findFather(b)] = findFather(a),那么这个集合的逻辑树中就会出现环,这是错误的,所以对于合并操作,我们一定要保证a和b处于两个不同的集合

int Union(int a, int b)
{
    // 并
    int fa = findFather(a), fb = findFather(b);
    if (fa != fb) // 防止成环
    {
        father[fa] = fb;
    }
}

对于本题来说,首先枚举邻接表中的每条边,将其端点用Union连通起来(一开始假设每个点都不连通)。然后枚举每个点,看看它是否满足集合根的定义(father[i] = i)。由上分析可知,每有一个点满足集合根的定义,就说明有一个连通块,而显然需要额外修建的边数等于连通块数-1。

下面贴本题的并查集代码:

// 并查集
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 1000
vector<int> ori[MAXN];
// 并查集的板子
int father[MAXN];
int n, m, k;
void init()
{
    // 初始化father数组
    for (int i = 0; i < MAXN; i++)
    {
        father[i] = i; // 一开始每个点都不连通
    }
}

int ff(int x)
{
    // 查
    int a = x;             // 保存x以便路径压缩
    while (x != father[x]) // 找爹
    {
        x = father[x];
    }
    while (a != father[a]) // 路径压缩
    {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}

int Union(int a, int b)
{
    // 并
    int fa = ff(a), fb = ff(b);
    if (fa != fb) // 防止成环
    {
        father[fa] = fb;
    }
}

// 板子结束

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) // 建邻接表
    {
        int f, t;
        cin >> f >> t;
        ori[f - 1].push_back(t - 1);
        ori[t - 1].push_back(f - 1);
    }
    for (int q = 0; q < k; q++)
    {
        int concern;
        cin >> concern;
        concern--;
        init();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < ori[i].size(); j++)
            {
                int u = i, v = ori[i][j]; // 枚举每条边,合并其两个端点
                if (u != concern && v != concern)
                {
                    Union(u, v);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (i != concern)
            {
                int fi = father[i];
                // cout << fi;
                if (fi == i)
                {
                    ans++;
                }
            }
        }

        if (q != 0)
        {
            cout << '\n';
        }
        cout << ans - 1;
    }
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments