跳转至

连通性相关

强联通分量缩点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
namespace SCC
{
    vector<int> G[MAX],T[MAX],scc[MAX]; 
    int dfn[MAX],low[MAX],tot;
    int vis[MAX],stk[MAX],top;
    int col[MAX],colsiz[MAX],num;

    void tarjan(int now)
    {
        dfn[now]=low[now]=++tot;
        stk[++top]=now,vis[now]=1;
        for(auto to:G[now])
            if(!dfn[to])
                tarjan(to),cmin(low[now],low[to]);
            else if(vis[to])
                cmin(low[now],dfn[to]);
        if(low[now]==dfn[now])
        {
            col[now]=++num,++colsiz[num],vis[now]=0,scc[num].eb(now);
            while(stk[top]!=now) col[stk[top]]=num,++colsiz[num],scc[num].eb(stk[top]),vis[stk[top]]=0,--top;
            --top;
        }
    }
    inline void ShrinkPoint() {for(int now=1;now<=n;++now) for(auto to:G[now]) if(col[now]!=col[to]) T[col[now]].eb(col[to]);}
}

割点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
namespace CutPoint
{
    vector<int> G[MAX];
    int dfn[MAX],low[MAX],tot;
    int root,cut[MAX],num;

    void tarjan(int now)
    {
        int flag=0;
        low[now]=dfn[now]=++tot;
        for(auto to:G[now])
            if(!dfn[to])
            {
                tarjan(to),cmin(low[now],low[to]);
                if(low[to]>=dfn[now])
                {
                    ++flag;
                    if((now!=root||flag>1)&&!cut[now]) cut[now]=1,++num;
                }
            }
            else cmin(low[now],dfn[to]);
    }
}

割边

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
namespace CutEdge
{
    struct edge{int nex,to;}e[MAX<<1];
    int head[MAX],cnt=1;
    inline void add(int x,int y) {e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y;}
    inline void Add(int x,int y) {add(x,y),add(y,x);}

    int dfn[MAX],low[MAX],tot;
    int bridge[MAX<<1],num;

    void tarjan(int now,int nowi)
    {
        dfn[now]=low[now]=++tot;
        for(int i=head[now],to=e[i].to;i;i=e[i].nex,to=e[i].to)
            if(!dfn[to])
            {
                tarjan(to,i),cmin(low[now],low[to]);
                if(low[to]>dfn[now]) bridge[i]=bridge[i^1]=1;
            }
            else if(i!=(nowi^1)) cmin(low[now],dfn[to]);
    }
}

点双联通分量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
namespace PDCC
{
    vector<int> G[MAX],pdcc[MAX];
    int dfn[MAX],low[MAX],tot;
    int stk[MAX],top,num;

    void tarjan(int now,int father)
    {
        int son=0;
        dfn[now]=low[now]=++tot;
        stk[++top]=now;
        for(auto to:G[now])
            if(!dfn[to])
            {
                tarjan(to,now),cmin(low[now],low[to]),++son;
                if(low[to]>=dfn[now])
                {
                    ++num,pdcc[num].eb(now);
                    do pdcc[num].eb(stk[top]),--top; while(stk[top+1]!=to);
                }
            }
            else if(to!=father) cmin(low[now],dfn[to]);
        if(!son&&!father) pdcc[++num].eb(now);
    }
}

边双连通分量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace EDCC
{
    struct edge{int nex,to;}e[MAX<<1];
    int head[MAX],cnt=1;
    inline void add(int x,int y) {e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y;}
    inline void Add(int x,int y) {add(x,y),add(y,x);}

    int dfn[MAX],low[MAX],tot;
    int bridge[MAX<<1],col[MAX],num;
    vector<int> edcc[MAX];

    void tarjan(int now,int nowi)
    {
        dfn[now]=low[now]=++tot;
        for(int i=head[now],to=e[i].to;i;i=e[i].nex,to=e[i].to)
            if(!dfn[to])
            {
                tarjan(to,i),cmin(low[now],low[to]);
                if(low[to]>dfn[now]) bridge[i]=bridge[i^1]=1;
            }
            else if(i!=(nowi^1)) cmin(low[now],dfn[to]);
    }
    void dfs(int now)
    {
        col[now]=num;
        if(now) edcc[num].eb(now);
        for(int i=head[now],to=e[i].to;i;i=e[i].nex,to=e[i].to) if(!col[to]&&!bridge[i]) dfs(to);
    }
}