概述
强连通分量
强连通图(Strongly Connected Graph \text{Strongly Connected Graph} Strongly Connected Graph )是指在有向图 G G G 中,如果对于每一对 v i , v j v_i,v_j v i , v j ,v i ≠ v j v_i≠v_j v i = v j ,从 v i v_i v i 到v j v_j v j 和从 v j v_j v j 到 v i v_i v i 都存在路径,则称 G G G 是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
(来源:百度百科 )
如上图所示,由节点1 , 2 , 3 1,2,3 1 , 2 , 3 构成的环组成一个强连通分量。
算法思路
Tarjan \text{Tarjan} Tarjan 算法(以发现者Robert Tarjan \text{Robert Tarjan} Robert Tarjan 命名)是一个在图中查找强连通分量的算法。
此算法以一个有向图作为输入,并按照所在的强连通分量给出其顶点集的一个划分。图中的每个节点只在一个强连通分量中出现,即使是在有些节点单独构成一个强连通分量的情况下(比如图中出现了树形结构或孤立节点)。
算法的基本思想如下:任选一节点开始进行深度优先搜索(若深度优先搜索结束后仍有未访问的节点,则再从中任选一点再次进行)。搜索过程中已访问的节点不再访问。搜索树的若干子树构成了图的强连通分量。
节点按照被访问的顺序存入堆栈中。从搜索树的子树返回至一个节点时,检查该节点是否是某一强连通分量的根节点并将其从堆栈中删除。如果某节点是强连通分量的根,则在它之前出堆栈且还不属于其他强连通分量的节点构成了该节点所在的强连通分量。
(来源:WikiPedia \text{WikiPedia} WikiPedia )
我们维护两个重要的数组d f n [ i ] dfn[i] df n [ i ] 和l o w [ i ] low[i] l o w [ i ] 。
d f n [ i ] dfn[i] df n [ i ] 是一个时间戳,代表节点i i i 被遍历到的次序,时间戳不可改变。
l o w [ i ] low[i] l o w [ i ] 代表该子树中,且仍在栈中的最小时间戳,l o w [ ] low[] l o w [ ] 相等的点在同一强连通分量中。
每次搜索要初始化dfn[x]=low[x]=++timer
(t i m e r timer t im er 初始值为0 0 0 ),每一个节点本身可视为一个强连通分量,因此将l o w [ x ] low[x] l o w [ x ] 暂时赋予时间戳,在搜索子树的过程中更新l o w [ x ] low[x] l o w [ x ] 。
当无法继续搜索时,如果d f n [ x ] = l o w [ x ] dfn[x]=low[x] df n [ x ] = l o w [ x ] ,说明找到了一个强连通分量。
过程模拟
给一张有向图。
从节点1 1 1 开始DFS \text{DFS} DFS ,把遍历到的节点加入栈中。搜索到节点x = 6 x=6 x = 6 时就无法向下继续搜索,d f n [ 6 ] = l o w [ 6 ] dfn[6]=low[6] df n [ 6 ] = l o w [ 6 ] ,找到了一个强连通分量。退栈直到栈顶元素为x x x 为止,于是找到$\{6\}$为一个强连通分量。
返回节点5 5 5 ,发现d f n [ 5 ] = l o w [ 5 ] dfn[5]=low[5] df n [ 5 ] = l o w [ 5 ] ,退栈后$\{5\}$为一个强连通分量。
返回节点3 3 3 ,继续搜索到节点4 4 4 ,把4 4 4 加入堆栈。发现节点4 4 4 向节点1 1 1 有后向边,节点1 1 1 还在栈中,所以l o w [ 4 ] = 1 low[4]=1 l o w [ 4 ] = 1 。返回3 3 3 ,3 3 3 还在栈中,更新l o w [ 3 ] = 1 low[3]=1 l o w [ 3 ] = 1 。
继续回到节点1 1 1 ,最后访问节点2 2 2 。4 4 4 还在栈中,所以更新l o w [ 2 ] = 5 low[2]=5 l o w [ 2 ] = 5 。返回1 1 1 后,发现d f n [ 1 ] = l o w [ 1 ] dfn[1]=low[1] df n [ 1 ] = l o w [ 1 ] ,把栈中节点全部取出,组成一个连通分量$\{1,3,4,2\}$。
至此,算法结束,求出了图中全部的三个强连通分量$\{1,3,4,2\},\{5\},\{6\}$。
可以发现,运行Tarjan \text{Tarjan} Tarjan 算法的过程中,每个顶点都被访问了一次,且只进出了一次堆栈,每条边也只被访问了一次,所以该算法的时间复杂度为O ( N + M ) O(N+M) O ( N + M ) 。
注意:Tarjan \text{Tarjan} Tarjan 算法一遍不一定能搜完所有的点。所以我们要对一趟跑下来还没有被访问到的点继续跑Tarjan \text{Tarjan} Tarjan ,判断依据就是看d f n [ i ] dfn[i] df n [ i ] 是否为0 0 0 。
模板
Tarjan缩点
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 30 31 32 33 34 35 36 37 38 39 40 41 42 int n,m;int timer;int stack[N],top;int deg[N];int dfn[N],low[N]; bool instack[N];int head[N],tot;int cnt;int belong[N];void tarjan (int x) { dfn[x]=low[x]=++timer; stack[++top]=x; instack[x]=1 ; int i; for (i=head[x];i;i=edge[i].Next) { int y=edge[i].to; if (!dfn[y]) { tarjan (y); low[x]=min (low[x],low[y]); } else if (instack[y]) low[x]=min (low[x],dfn[y]); } if (dfn[x]==low[x]) { int y; cnt++; do { y=stack[top--]; instack[y]=false ; belong[y]=cnt; }while (x!=y); } }
洛谷 P3387 【模板】缩点
Enter \text{Enter} Enter
题目背景
缩点+DP
题目描述
给定一个 n n n 个点 m m m 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。
输入格式
第一行两个正整数 n , m n,m n , m
第二行 n n n 个整数,依次代表点权
第三至 m + 2 m+2 m + 2 行,每行两个整数 u , v u,v u , v ,表示一条 u → v u\rightarrow v u → v 的有向边。
输出格式
共一行,最大的点权之和。
输入输出样例
输入 #1
2 2
1 1
1 2
2 1
输出 #1
2
说明/提示
【数据范围】
对于 100 % 100\% 100% 的数据,1 ≤ n ≤ 1 0 4 1\le n \le 10^4 1 ≤ n ≤ 1 0 4 ,1 ≤ m ≤ 1 0 5 1\le m \le 10^5 1 ≤ m ≤ 1 0 5 ,点权 ∈ [ 0 , 1000 ] \in [0,1000] ∈ [ 0 , 1000 ]
算法:Tarjan \text{Tarjan} Tarjan 缩点 + \text{+} + DAGdp \text{DAGdp} DAGdp
代码
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 #include <queue> #include <iostream> #include <cstring> #include <cstdio> #define N 10005 using namespace std;int n,m;int timer;int stack[N],top;int deg[N];int dfn[N],low[N]; bool instack[N];int head[N],tot;int p[N];int val[N];int representative[N];int new_head[N],new_tot;struct E { int from; int to; int Next; }; E edge[N*10 ],new_edge[N*10 ]; void add (int u,int v) { tot++; edge[tot].to=v; edge[tot].from=u; edge[tot].Next=head[u]; head[u]=tot; } void tarjan (int x) { dfn[x]=low[x]=++timer; stack[++top]=x; instack[x]=1 ; int i; for (i=head[x];i;i=edge[i].Next) { int y=edge[i].to; if (!dfn[y]) { tarjan (y); low[x]=min (low[x],low[y]); } else if (instack[y]) low[x]=min (low[x],dfn[y]); } if (dfn[x]==low[x]) { int y; do { y=stack[top--]; representative[y]=x; instack[y]=0 ; if (x!=y) p[x]+=p[y]; }while (x!=y); } } int toposort () { queue<int >q; int i; for (i=1 ;i<=n;i++) { if (representative[i]==i&&!deg[i]) { q.push (i); val[i]=p[i]; } } while (!q.empty ()) { int x=q.front (); q.pop (); for (i=new_head[x];i;i=new_edge[i].Next) { int y=new_edge[i].to; val[y]=max (val[y],val[x]+p[y]); deg[y]--; if (!deg[y]) q.push (y); } } int ans=0 ; for (i=1 ;i<=n;i++) ans=max (ans,val[i]); printf ("%d\n" ,ans); } void init () { tot=0 ; timer=0 ; top=0 ; new_tot=0 ; memset (head,0 ,sizeof (head)); memset (dfn,0 ,sizeof (dfn)); memset (instack,0 ,sizeof (instack)); memset (deg,0 ,sizeof (deg)); memset (new_head,0 ,sizeof (new_head)); memset (representative,0 ,sizeof (representative)); memset (val,0 ,sizeof (val)); } void solve () { init (); scanf ("%d%d" ,&n,&m); int i; for (i=1 ;i<=n;i++) scanf ("%d" ,&p[i]); for (i=1 ;i<=m;i++) { int u,v; scanf ("%d%d" ,&u,&v); add (u,v); } for (i=1 ;i<=n;i++) { if (!dfn[i]) { tarjan (i); } } for (i=1 ;i<=m;i++) { int x=representative[edge[i].from]; int y=representative[edge[i].to]; if (x!=y) { new_edge[++new_tot].from=x; new_edge[new_tot].to=y; new_edge[new_tot].Next=new_head[x]; new_head[x]=new_tot; deg[y]++; } } toposort (); } int main () { solve (); return 0 ; }