浅谈一种使用并查集进行强连通缩点的方法

liangbob · 2024-04-07 22:39:19 · 算法·理论

背景

来源于本校老师的一种并查集进行强连通缩点的方式。

点的分类

我们将点分为三种状态：

• 访问完。
• 正在访问：当搜索到一个结点后，正在递归搜索其邻接结点，那么这个结点就是正在访问。
• 还没访问：暂时没递归到。

情况一：递归回来了

当一个结点 u 递归着递归着递归到一个正在访问的结点 v 时：

• 说明 u 和 v 之间相互可达。

  由于 v 正在访问，这也意味着他是在递归其邻接结点时发现了 u，而 u 又递归到了 v，那么两者相互可达。

• 即，u 和 v 同属于一个强连通分量。

那么我们就可以用并查集合并这两个点。

情况二：递归到访问过的点

当递归到访问到的点时，根据定义，他的邻接结点肯定都搜索完毕了，那么这个点就不用搜，直接跳过。

实现时，我们直接搜没搜过的邻接结点就行。

合并时的细节

现在，我们要修改一下情况一中的说法，当结点 u 递归着递归着递归到一个并查集祖先正在访问的结点 v 时合并这两个点。

为什么要强调“并查集祖先”呢？

抽象的想，一个点代表的不仅是它本身，更是它所在的强连通分量，如果祖先正在访问，意味着这个分量正在“招新”，接纳新的结点。

根据并查集，这个 v 相当于这个分量的使者，负责接纳新成员，他与 u 合并就相当于 u 和 v 所在的分量合并，更确切的说，是 u 所在分量与 v 所在分量合并。

这里再补充几点：

• “极大强连通子图”，“极大”意味着一个分量需要不断地招新，不断地招新，直到招不到为止。

• 根据强连通分量的定义，一个连通分量内部互相可达。假设 u 和 v 互相可达，根据定义，u 所在分量的其它点都可到达 u，v 所在分量的其它点都可到达 v，又由于 u 和 v 互相可达，那么 u 所在分量的其它点可以靠这条可达路径到 v 以及 v 所在分量的其它点，v 所在分量的其它点可以靠这条可达路径到 u 以及 u 所在分量的其它点，因此这两个点所在的分量可以合并成一个。

然后最关键的来了：

合并的时候需要注意，要把祖先“深度”大的点合并到祖先“深度”小的点去。此处的“深度”指进入“正在搜索”状态的先后编号，小的先。

这个所谓祖先的深度其实就是 low 数组，也就是某个点祖先的 dfs 序。贪心地想，如果把深度小的当作祖先，那么，就可能有更多的结点加入。这个可能需要感性理解，也是最难理解的一点。

维护深度非常简单，直接在进入“正在搜索”状态时更新一下即可。

本质

我们发现，我们其实在用并查集祖先的深度来维护这个点的 low 值，即能够回溯到的最早的结点。所谓并查集祖先正在访问，其实就是还在栈中。所以说，这个算法与 Tarjan 算法的本质是一样的。只不过这个算法使用了并查集来维护强连通分量，使用“深度”的概念代替了原来的 dfs 序（其实也不叫代替，和原来 dfs 序是差不多的）。

因此，此算法正确性证明同 Tarjan 算法，复杂度亦为 O(n+m)（如果将 find 函数的复杂度视为 O(1) 的话）。

实际上，Tarjan 算法所具有的编号为逆拓扑序的性质在该算法中亦存在，不过编号变成了并查集祖先结点访问完毕的顺序编号（各位可以比照 Tarjan 算法进行理解），并且不是连续的（你把它离散化一下就是连续的了）。

流程

• 遍历所有子结点。
• 如果没访问，更新深度，递归访问它。
• 如果它的并查集祖先访问过了（即存在一个确定的强连通分量），那么将这个结点与它合并。注意要把把祖先“深度”大的点合并到祖先“深度”小的点去。
• 遍历完后，将这个结点的状态设置为访问完。
• 所有结点都遍历完后，并查集内的连通块即为强连通分量。

代码实现中，直接用深度为 0 表示没访问，深度为 -1 表示为访问完。

例题：P4782

分析

2-SAT 板子。将一个变量拆成两个点表示这个变量为真或者为假，然后按照题意进行连边。显然，此时这两个点不能再同一个强连通分量中。

对于构造，我们需要取所在分量拓扑序较大的那个对应结点（正确性证明可以见题解区）。由于我们只需要比较拓扑序大小，因此无需对逆拓扑序进行离散化。

代码

#include <bits/stdc++.h> 
#define endl '\n'
#define int long long
#define IL inline
using namespace std;
const int N = 1e7 + 10;

int n, m, fa[N], w[N], tp[N], cur;
vector <int> g[N];

int find(int x)
{
    return (x == fa[x] ? x : fa[x] = find(fa[x])); 
}

void dfs(int u)
{
    for(int v : g[u])
    {
        if(!w[v]) //未访问
        {
            w[v] = w[u] + 1; //更新深度
            dfs(v);
        }
        int fu = find(u), fv = find(v);
        if(w[fv] > 0) //祖先未访问
        {
            if(w[fu] > w[fv]) fa[fu] = fv; //合并到深度小的
            else fa[fv] = fu;
        }
    }
    w[u] = -1; //已访问完
    tp[u] = ++cur; //记录顺序
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> n >> t;
    while(t--)
    {
        int i, a, j, b;
        cin >> i >> a >> j >> b;
        //建图
        add(i + n * (a & 1), j + n * (b ^ 1));
        add(j + n * (b & 1), i + n * (a ^ 1));
    }
    n *= 2;
    iota(fa + 1, fa + n + 1, 1);
    for(int i = 1;i <= n;i++)
    {
        if(!w[i]) //如果未访问
        {
            w[i] = 1; //初始化访问深度
            dfs(i);
        }
    }
    int y = n / 2;
    for(int i = 1;i <= y;i++)
    {
        if(find(i) == find(i + y)) //在同一个分量里
        {
            cout << "IMPOSSIBLE" << endl;
            return 0;
        }
    }
    cout << "POSSIBLE" << endl;
    for(int i = 1;i <= y;i++)
    {
        if(tp[find(i)] < tp[find(i + y)]) cout << 1 << ' '; //比较强连通分量的拓扑序
        else cout << 0 << ' ';
    }
    return 0;
}