连通性相关

约 527 个字 197 行代码 预计阅读时间 4 分钟

强连通

有向图，任意两点连通

强连通分量缩点

vector<int> e[N], sta, ne[N];
array<int,2> ed[N];
int dfn[N], low[N], f[N], vis[N],in[N],dfsOrder, sccnum;
void init(int n)
{
    dfsOrder = sccnum = 0;
    for (int i = 1; i <= n; ++i)
        e[i].clear();
    sta.clear();
    memset(vis, 0, sizeof(int) * (n + 1));
    memset(dfn,0,sizeof(int)*(n+1));
    memset(in,0,sizeof(int)*(n+1));
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++dfsOrder;
    sta.push_back(u);
    vis[u] = 1;
    for (auto &v : e[u])
    {
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] != low[u])
        return;
    ++sccnum;
    vector<int>::iterator it=(--sta.end());
    for(f[u]=sccnum,vis[u]=0;*it!=u;--it)
        f[*it]=sccnum,vis[*it]=0;
    sta.erase(it,sta.end());
}
void makeNewMap(int n,int m)
{
    for(int i=1;i<=n;++i)
        if(!in[i])
            tarjan(i);
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i);
    for (int i = 0;i<m;++i)
    {
        int u=f[ed[i][0]],v=f[ed[i][1]];
        if(u==v)
            continue;
        ne[u].push_back(v);
    }
}

割点

如果删除一个点后，这个图的极大连通分量数增加，那么该点为割点

记录每个点的dfs序（dfn），和不通过其父亲能到达的最小dfs序（low）

如果点u的一个儿子v，不能回到祖先（$low_v\ge dfn_u$），那么u为割点

但是对于起点不适用，起点需要有至少2个儿子，才是割点

vector<int> e[N];
int dfn[N],low[N],dfsOrder,cut[N];
void tarjan(int u,int fa)
{
    low[u]=dfn[u]=++dfsOrder;
    int child=0;
    for(int &v:e[u])
    {
        if(!dfn[v])
        {
            ++child;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(u!=fa && low[v]>=dfn[u])
                cut[u]=1;
        }
        else if(v!=fa)//有向图改为else
            low[u]=min(low[u],dfn[v]);
    }
    if(fa==u && child>=2)
        cut[u]=1;
}
void findCutVertex(int n)
{
    for(int i=1;i<=n;++i)
    {
        if(!dfn[i])
            tarjan(i,i);
    }
}

割边

删边，其他类似割点

修改一处：$low_v>dfn_u$，且不需要特殊处理根节点

u-bridge[u] 是一条割边

一些性质

割边的两边一般是割点，除非只有一个点

vector<int> e[N];
int dfn[N],low[N],dfsOrder,bridge[N];
void tarjan(int u,int fa)
{
    low[u]=dfn[u]=++dfsOrder;
    for(int &v:e[u])
    {
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                bridge[v]=u;
        }
        else if(v!=fa)//有向图改为else
            low[u]=min(low[u],dfn[v]);
    }
}
void findBridge(int n)
{
    for(int i=1;i<=n;++i)
    {
        if(!dfn[i])
            tarjan(i,i);
    }
}

边双连通

没有割边的连通图是边双连通，点的边双连通具有传递性

边双连通分量缩点

tarjan访问每个点时把点进栈，当一个点 u 的后续点都访问完时，如果 u 是一个极大边双连通分量的，第一个访问的点，把栈内的点都拿出来，直到 u。同时给原来的点做一个映射。同一个映射的点，在同一个边双

新图可能需要旧图的信息，所以旧图的边信息存两份

vector<int> e[N],sta,ne[N];
array<int,2> ed[N];
int dfn[N],low[N],f[N],dfsOrder,bccnum;
void init(int n)
{
    dfsOrder=bccnum=0;
    for(int i=1;i<=n;++i)
        e[i].clear();
    sta.clear();
}
void tarjan(int u,int fa)
{
    low[u]=dfn[u]=++dfsOrder;
    sta.push_back(u);
    for(int &v:e[u])
    {
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(v!=fa)//有向图改为else
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]!=dfn[u])
        return;
    ++bccnum;
    while(bcc.back()!=u)
    {
        f[bcc.back()]=bccnum;
        bcc.pop_back();
    }
    f[u]=bccnum;
    bcc.pop_back();
}
void makeNewMap(int m)
{
    tarjan(1,1);
    for(int i=0;i<m;++i)
    {
        int u=f[ed[i][0]],v=f[ed[i][1]];
        if(u==v)
            continue;
        ne[u].push_back(v);
    }
}

点双连通

没有割点的连通图是点双连通，点的点双连通不具有传递性

除了仅包含两个点一条边的点双外，其他点双都满足：任意两点间都存在至少两条点不重复路径(起点终点除外)

任意一个不是割点的点都只存在于一个点双中，割点也一定属于两个及以上的点双

两个点双至多存在一个公共点——割点

点双连通分量缩点

vector<int> e[N], sta;
int dfn[N], low[N], dfsOrder;
vector<vector<int>> ans;
void tarjan(int u, int fa)
{
    low[u] = dfn[u] = ++dfsOrder;
    sta.push_back(u);
    for (auto &v : e[u])
        if (!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u])
            {
                vector<int> tmp;
                while (sta.back() != v)
                {
                    tmp.push_back(sta.back());
                    sta.pop_back();
                }
                sta.pop_back();
                tmp.push_back(v);
                tmp.push_back(u);
                ans.push_back(tmp);
            }
        }
        else if (v != fa) // 有向图改为else，重边需判断是否同一条无向边
            low[u] = min(low[u], dfn[v]);
}
void makeNewMap(int n)
{
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
        {
            tarjan(i, -1);
            if (e[i].empty())//需去除自环
            {
                vector<int> tmp;
                tmp.push_back(i);
                ans.push_back(tmp);
            }
        }
}

圆方树

原来的每个点对应一个圆点，每一个点双对应一个方点

对于每一个点双，它对应的方点向这个点双中的每个点连边

如果原图连通，则“圆方树”才是一棵树