强联通分量 » 老官童鞋gogo的博客

强联通分量简介

定义

在有向图$G$中，如果两个顶点$u,v$间有一条从$u$到$v$的有向路径，同时还有一条从$v$到$u$的有向路径，即：两个点可以互相到达，则称两个顶点强连通。如果有向图$G$的每两个顶点都强连通，称$G$是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。

强联通分量算法

Tarjan算法

主要作用

缩点
求无向图的割点与桥

缩点就是把一张有向有环图中的环缩成一个点，形成一个有向无环图。

桥是存在于无向图中的这样的一条边，如果去掉这一条边，那么整张无向图会分为两部分，这样的一条边称为桥无向连通图中，如果删除某边后，图变成不连通，则称该边为桥。

割点无向连通图中，如果删除某点后，图变成不连通，则称该点为割点。

原理（缩点）

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

做法（缩点）

再Tarjan算法中，有如下定义。

$ dfn[i] $: 在DFS中该节点被搜索的次序(时间戳)

$ low[i] $: 为$i$或$i$的子树能够追溯到的最早的栈中节点的次序号

一个栈$s[top]$，在栈中的元素表示待处理的元素，靠近栈底的元素是靠近栈顶元素的祖先。

当时dfn[i]==low[i]时，为$i$或$i$的子树可以构成一个强连通分量。

简单来说，数组$ dfn[i] $表示搜索到第$ i $的时间，数组$ low[i] $用来判断当前节点是否能够回到之前的节点，即判断环。

举例：如图：

图片已经不存在，对不起……

我们模拟一下，从$ 1 $号点开始，记下$dfn[1]=now,low[1]=now$，入栈，这里的$now$表示时间，目前的值为$1$，然后搜索$1$号点的下一个点$2$，$2$号点没有被搜索过，记下$dfn[2]=now,low[2]=now$，入栈，此时的$now$的值为$2$ ……搜索完点$6$时，发现$6$是以$3$为根的子树的最后一个点，这时候向后回溯，发现dfn[6]==low[6]，点$6$出栈，我们就可以判断得出，$6$这个点是一个强联通分量，随后将，向后回溯，dfn[3]==low[3]，点$3$出栈，同样的，$3$也是一个强联通分量，继续向后回溯，当我们到了点$2$的时候我们还可以另外一个方向DFS，那么就去搜索点$5$，点$5$没有被搜索过，记下$dfn[5]=now,low[5]=now$，入栈，此时的$now$的值为$5$，继续向下，搜索到了点$6$，点$6$我们之前搜索过，并且已经不再栈内，跳过，继续搜索点$1$，而点$1$我们搜索过，并且当前的点$1$还在栈中，那么判断$low[1]$和$low[5]$的大小，将$low[5]$赋值为$low[1]$和$low[5]$中的较小值，这样做的目的是判断谁是先更早加入栈中的，即谁是谁的祖先，那么赋值$low[5]=low[1]=1$。剩下所有点同理，最终回溯到点$1$，到了点$1$我们发现dfn[1]==low[1]那么我们开始回溯，假设当前的点为$v$，要回溯到点$u$，那么我要对$low[u]$重新赋值为$low[v]$和$low[u]$的较小的值，回到根节点后，开始缩点。从栈顶开始，即从$1$的最小儿子开始，一直搜到根节点$1$。过程中每次搜到的点都会与点$1$缩成一个点，如果每个点都有权值，就在搜索栈的过程中相加，最终成功将一个环缩成一个点。但是，这仅仅是以$1$为根节点的树，对于图中我们没有遍历到的点都要重新跑一边Tarjan。

分析其中的过程，我们总结出，对于一个节点$i$，如果dfn[i]==low[i]那么说明这是一个强联通分量的根节点，我们要从栈顶一直弹出到这个根节点，所有弹出的元素就是形成这环的所有点。

最后，对于缩点，我们要重新枚举原来的边，将边两边的点所属的缩点后的点连接。

代码（缩点）

来源：洛谷：P3387 【模板】缩点

这道题除了上面讲的缩点，还要输出一条路径上最大的点权和，一个点只能取一次，很明显可以把一个环缩成一个点来做。Tarjan缩点完成后，记录下缩点后的拓扑序，进行动态规划（原因？拓扑排序解决DP无后效的问题）。

动态规划状态：设$dp[i]$表示从第一个点到第i个点的最大点权和

动态规划转移方程：$$dp[i]=max{dp[i],dp[last[i][k-1]]+Dis[i]}$$

其中的变量名$last[i][k-1]$表示第$i$个点的上一个点，$Dis[i]$表示第$i$个点的点权。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 1000001
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct Node
{
    int nxt,to,fr;//结构体内存储nxt，表示这一条边的下一条边，to表示指向的点，fr表示当前的点
}e[100001],E[100001];
int n,m,g[100001],G[100001],tp[100001],inp[100001],s[100001],low[100001],dfn[100001],tpnow,now,dp[100001],ans,nxt,Nxt,tot,top,a[100001],A[100001],dis[100001],Dis[100001],vis[100001];
vector<int>last[100001];//变量很多，我会在过程中逐个解释
void add(int x,int y)//建立缩点之前的边
{
    e[++nxt].to=y;
    e[nxt].fr=x;
    e[nxt].nxt=g[x];
    g[x]=nxt;
}
void addE(int x,int y)//建立缩点之后用于计算最大点权和的边（缩点以后的数组统统以大写字母表示）
{
    E[++Nxt].to=y;
    E[Nxt].fr=x;
    E[Nxt].nxt=G[x];
    G[x]=Nxt;
}
void tarjan(int x)//x表示当前子树下的根节点
{
    dfn[x]=low[x]=++now;//dfn[i]与low[i]的作用与原理解释部分相同，搜索到根节点的时间为now
    vis[x]=1;//vis[i]记录当前节点i是否在栈中出现
    s[++top]=x;//s[i]的作用与原理解释部分相同，压入栈
    for(int k=g[x];k;k=e[k].nxt)//遍历边
    {
        int y=e[k].to;
        if(dfn[y]==0)//如果指向的节点没有被访问过，就把指向的节点看作是根节点，判断指向节点下的强连通分量
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);//将当前节点的low值修改，修改成能够形成强连通分量的时间最早的根节点
        }
        else if(vis[y]!=0)//如果当前节点被搜索到但仍在栈中
        {
            low[x]=min(low[x],low[y]);//将当前节点的low值修改，修改成指向节点所形成强连通分量的根节点和自身所形成强连通分量的根节点中时间更早的那一个
        }
    }
    if(low[x]==dfn[x])//如果自己就是一个强连通分量的根节点
    {
        tot++;//tot表示强连通分量个数，强连通分量的个数+1
        while(1)//遍历栈
        {
            A[s[top]]=tot;//A[i]表示第i个点属于第几个强连通分量，让当前栈顶元素属于第tot个强连通分量
            Dis[tot]+=dis[s[top]];//Dis[i]表示第i个强连通分量的总点权值是多少，将过程中的点权值相加
            vis[s[top]]=0;//将栈中标记清除
            if(x==s[top--])//直到到了当前强连通分量的根节点，退出循环
                break;
        }
    }
}
void topo()//拓扑排序
{
    queue<int>q;//q表示拓扑排序所用的队列
    for(int i=1;i<=tot;i++)
    {
        if(inp[i]==0)//入度为0进队列
            q.push(i);
    }
    while(!q.empty())//经典拓扑排序，其中拓扑序被保存到tp[]这个数组中
    {
        int now=q.front();
        q.pop();
        tp[++tpnow]=now;
        for(int k=G[now];k;k=E[k].nxt)
        {
            int y=E[k].to;
            inp[y]--;
            if(inp[y]==0)
                q.push(y);
        }
    }
}
int main()
{
    n=read(),m=read();//n表示点数，m表示边数
    for(int i=1;i<=n;i++)
    {
        dis[i]=read();//dis[i]表示点权
    }
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        add(x,y);//建边
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)//如果当前的节点没有访问过，就进行一边Tarjan
            tarjan(i);
    }
    for(int i=1;i<=m;i++)//链接缩点后的点
    {
        int x=e[i].fr,y=e[i].to;
        if(A[x]!=A[y])
        {
            inp[A[y]]++;//A[y]这个点的入度+1
            addE(A[x],A[y]);
            last[A[y]].pb(A[x]);//last[i]是一个vector，表示缩点后第i个节点的所有指向的点，在遍历过程中第二维的值要-1，因为vector从地址0开始存储
        }
    }
    topo();//拓扑排序
    for(int i=1;i<=tot;i++)
    {
        int w=tp[i];//去除拓扑序中第i个位所表示的点
        dp[w]=Dis[w];//动态规划
        for(int k=1;k<=last[w].size();k++)
        {
            dp[w]=max(dp[w],dp[last[w][k-1]]+Dis[w]);
        }
    }
    for(int i=1;i<=tot;i++)
    {
        ans=max(ans,dp[i]);//统计答案
    }
    printf("%d",ans);
    return 0;
}