图的连通性算法总结

Wangxun · 2023-03-13 14:32:38 · 个人记录

图的连通性算法

NFLSOJ 链接1

NFLSOJ 链接2

图的连通性分为有向图的连通性和无向图的连通性。

有向图的连通性

有向图的连通性一般指强连通。

强连通图：对于有向图 G，其中的任意两点可达，则 G 为强连通图。
强连通分量：极大的强连通图。

Kosaraju 算法

对于一张图，在原图中进行 dfs，并用一个数组记录点被遍历的先后顺序。然后建出它的反图，在反图中根据原顺序倒着进行 dfs，每次 dfs 搜出的一些点构成一个强连通分量。

极其简单，模板不放了。

Tarjan 算法

int low[N],dfn[N],bel[N],times = 0,cnt = 0;
stack<int> s;
void tarjan(int u)
{
    low[u] = dfn[u] = ++times;
    s.push(u);
    for(register int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!bel[v]) low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        ++cnt;  
        while(s.size())
        {
            int v = s.top();
            s.pop();
            bel[v] = cnt;   
            if(v == u) break;   
        }   
    }       
}

强连通分量缩点

把每一个强连通分量当成一个点，进行连边，可以证明缩点后的图是一个 DAG（有向无环图），可以解决一些实际问题。

F(u,1,n)
    for(register int i = head[u];i;i = nxt[i])
    {
        u = bel[u]
        int v = bel[to[i]];
        if(u == v) continue;
        add(u,v);
    }

无向图的连通性

注意，无向图可能不连通，所以 tarjan 算法一定要 for 循环。

并查集

想到无向图的连通性，首先应该想到并查集。

我们之前的并查集，可以支持合并操作，并查询两个点是不是在同一个连通块内。

但如果要维护图的连通性，结合线段树分治，可能需要用到撤回操作。

之前的并查集在合并时路径压缩，无法删除。然而，我们不进行路径压缩进行合并，是可以撤回的，这叫按秩合并。

然而，为了保证时间复杂度，我们要记一个 size，把小的合并到大的中，可以证明时间复杂度是 O(\log{n}) 的，这叫启发式合并。

于是，我们的并查集变成了这样：

struct union_find
{
    int sz[N],f[N];
    stack<pii> s;
    inline void clear()
    {
        F(i,1,n) sz[i] = 1,f[i] = i;    
    }
    inline int find(int u)
    {
        while(u != f[u]) u = f[u];
        return u;
    }
    inline bool merge(int u,int v)
    {
        u = find(u),v = find(v);
        if(u == v) return 0;
        if(sz[u] < sz[v]) swap(u,v);
        sz[u] += sz[v];
        f[v] = u;
        s.push((pii){u,v});
        return 1;
    }
    inline void erase()
    {
        int u = s.top().first,v = s.top().second;
        s.pop();
        f[v] = v;
        sz[u] -= sz[v];
    }
}tree;

注：实际上，并查集也可以可持久化，但这可以使用可持久化线段树来维护，应用不广泛，故不整理。

桥和边双连通分量

在一个无向图中，对于一条边 E，如果删去这条边后原图不连通，则这条边被称为桥。
边双连通分量是原图 G 一张极大的不含有桥的子图。

Tarjan 算法

int dfn[N],low[N],times = 0;
void tarjan(int u,int fa)
{
    dfn[u] = low[u] = ++times;
    for(register int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u]) bridge[i] = bridge[i^1] = 1,++ccb;
        } 
        else if(i != (fa ^ 1)) low[u] = min(low[u],dfn[v]);
    }
}

求边双连通分量自然可以用栈记录。

int dfn[N],low[N],bel[N],times = 0,cnt = 0;
stack<int> s;
void tarjan(int u,int fa)
{
    s.push(u);
    dfn[u] = low[u] = ++times;
    for(register int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u] = min(low[u],low[v]);
        }
        else if(i != (fa ^ 1)) low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        ++cnt;
        while(s.size())
        {
            int v = s.top();
            s.pop();
            bel[v] = now;
            if(u == v) break;
        }
    }
}

但有一个方法。任选一个未遍历过的点，进行 dfs，只走非桥的边，遍历到的这些点构成一个边双连通分量。

int bel[N],cnt = 0;
bitset<N> vis; 
void dfs(int u)
{
    bel[u] = cnt;
    vis[u] = 1;
    for(register int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(bridge[i]||vis[v]) continue;
        dfs(v);  
    }           
}
// 以下是 main 函数的内容 
F(i,1,n)
    if(!vis[i])
    {
        ++cnt;
        dfs(i);
    }

缩点

边双连通分量也可以缩点，方法和强连通分量类似，就不赘述了。

割顶和点双连通分量

割顶：对于无向图中的一个点 u，如果去掉该点原图不连通，则该点为原图的一个割顶。
边双连通分量是原图一张极大的不含对于子图不含有割顶的子图。

tarjan 算法

求割点。

int dfn[N],low[N],times = 0,cnt = 0;
bitset<N> cut;
void tarjan(int u,int fa)
{
    low[u] = dfn[u] = ++times;
    int child = 0;
    for(int i = 0;i < (int)g[u].size();++i)
    {
        int v = g[u][i];
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u]) ++child;
        }
        else if(v != fa) low[u] = min(low[u],dfn[v]);
    }
    if(child >= 2||(fa&&child == 1)||(!fa&&!child))
    {
        cut[u] = 1;
        ++cnt;
    }
}

或者

int dfn[N],low[N],times = 0,bcc = 0;
vector<int> ans[N];
bitset<N> cut;
stack<pii> s;
void tarjan(int u,int fa) 
{
    s.push(u);
    low[u] = dfn[u] = ++times;
    int son = 0;
    for(int i = fir[u]; i; i = nxt[i]) 
    {
        int v = to[i];
        if(!dfn[v]) 
        {
            ++son;
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u]) 
            {
                bcc++;
                while(s.size()) 
                {
                    int x = s.top();
                    ans[bcc].push_back(x);
                    if(x == v) break;
                }
                ans[bcc].push_back(u);
            }
        } 
        else if(v != fa) low[u] = min(low[u],dfn[v]);
    }
    if(!fa&&!son) ans[++bcc].push_back(u);
}

缩点

实际上，由于割点可能出现在多个点双中，对于点双连通分量缩点的结果是一颗圆方树。

int dfn[N],low[N],times = 0,cnt;
stack<int> s;
vector<int> g[N<<1];
void tarjan(int u)
{
    low[u] = dfn[u] = ++times;
    s.push(u);
    for(register int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u]) 
            {
                ++cnt;
                while(s.size())
                {
                    int x = s.top();
                    s.pop();
                    g[x].push_back(cnt);
                    g[cnt].push_back(x); 
                    if(x == v) break;
                }   
                g[u].push_back(cnt);
                g[cnt].push_back(u);
            }
        }
        else low[u] = min(low[u],dfn[v]);
    }
}
// 以下是 main 函数
cnt = n;
F(i,1,n)
    if(!dfn[i])
    {
        tarjan(i);  
        s.pop();
    }

其中，新建的点是方点，原来的点是圆点。

这样，就可以在图上进行树链剖分等一系列操作了！

图的连通性算法总结