在算法题中我们时常会遇到有向图上的连通性问题比如求从起点到终点最多能收集多少硬币或者判断整张图是否任意两点都互相可达。对于无环的有向图DAG我们可以轻松地用拓扑排序进行 DP时间复杂度仅为 O(nm)。然而一旦图中出现了环情况就变得棘手环的存在导致无法直接拓扑排序朴素的 DFS/BFS 很难处理环中的最优决策。那么有没有一种方法能够将有环图“拍平”使其变成 DAG从而继续享受拓扑排序的便利呢答案是肯定的。我们可以引入一种设计巧妙的图论组合强连通分量SCC缩点配合Tarjan 算法它可以在 O(nm) 的线性时间内完成缩点并且还能自然推广到2‑SAT等经典问题的求解(本文参考 https://www.bilibili.com/video/BV18u6FBmEXc/https://www.bilibili.com/video/BV1qNdvBwEGa/由于我是蒟蒻所以只学了一部分QWQ)1.SCC与缩点的相关概念(1)SCC的概念SCC即强连通分量是指一个有向图中保证所有点都可以互相到达的最大子图一个连通图里也可能包括多个强连通分量(2)缩点的概念我们可以把SCC看成一个点当然前提是不影响最终答案这样原图就变成了一个DAG即有向无环图由于没有了环处理起来就会简单许多最常见的是用拓扑排序处理2.Tarjan算法求解SCC(1)Tarjan算法的基本概念①三种边在遍历图的过程中我们可以把遇见的边分为3种我们可以类比三色DFS来理解这三种边树边未遍历过的边其另一头上的点的dfn序号也没有分配过回边另一头上的点分配过dfn序号但没有分配到某个强连通分量的边弃边另一头上的点分配过dfn序号和某个强连通分量的边如上面的图a-bb-cc-d都为树边,d-b为回边若从d经过了efg确定了efg为一个SCC,则之后回溯到cc-h为树边h-a为回边h-g为弃边②dfn[u]:节点u分配的dfn序号③low[u]从u及其子树上点最多走一条回边到达最上面即序号最小的点的dfn序号如dfn[a] 1;则b通过b-h和回边h-a到adfn[b] 1以及d通过回边d-b到达b dfn[d] dfn[b] dfn[a]再比如g最高就无法到达a只能到达e于是dfn[g] dfn[e]④belong[u],节点u分配的scc序号如果等于0说明还未分配⑤遍历时准备一个栈sta将遇到的节点弹入栈中如果该节点分配了SCC就从栈里弹出(2)Tarjan算法的基本思路tarjan算法就像是判断一个点能不能兜住所在scc所有的点判断核心就是low无法找到更上层的点就说明这个点是所在scc的最高层①除了设置之前提到的dfn,low,belong以外我们还需要cnt记录dfs遍历点的编号以及sccCnt记录scc的编号设为全局变量并初始化为0②首先自增cnt并将其赋值给low[u]和dfn[u]③然后遍历他的所有子树如果是树边即dfn[v]未分配0的先继续递归调用tarjan(v),再计算low数组low[u] min(low[u],low[v])否则如果是回边即belong未初始化而等于0直接计算low[u] min(low[u],dfn[v])如果是弃边不做任何处理④如果编号dfn[u]等于low[u]说明其能兜住这个scc先自增sccCnt再不断出栈直到u自己出栈同时出栈的元素s的belong赋值sccCnt⑤从1到n循环如果发现dfn[i]等于0说明其未被遍历到调用tarjan(i);此外有一个很常见的问题在遇到回边时将low[u] min(low[u],dfn[v])改为low[u] min(low[u],low[v])从结果上看也正确然而如果这么做会导致low的定义模糊前者能明确体现出回边只能经过一条而后者却由于某些节点没有遍历到v导致调用low[v]不一定是最向上的点因此不利于理解然而low作用只在于判断能否兜住scc越往上反而越能兜住所以从v再向上走不影响最终结果但因为方便理解我们通常还是选用第一种写法例题链接https://www.luogu.com.cn/problem/B3609 示例代码如下#includebits/stdc.husingnamespacestd;usinglllonglong;constintMOD1e97;intn,m;vectorvectorintadj;vectorintdfn,low,belong;intsccCnt0,cnt0;stackintst;voidtarjan(intu){dfn[u]low[u]cnt;st.push(u);for(intv:adj[u]){if(dfn[v]0){tarjan(v);low[u]min(low[u],low[v]);}elseif(belong[v]0){low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){sccCnt;ints;do{sst.top();st.pop();belong[s]sccCnt;}while(s!u);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);intu0,v0;cinnm;adj.resize(n1);for(inti0;im;i){cinu0v0;adj[u0].push_back(v0);}dfn.resize(n1,0);low.resize(n1,0);belong.resize(n1,0);for(inti1;in;i){if(dfn[i]0)tarjan(i);}coutsccCnt\n;vectorboolflag(n1,false);for(inti1;in;i){if(!flag[i]){intsccbelong[i];for(intj1;jn;j){if(belong[j]scc){coutj ;flag[j]true;}}cout\n;}}return0;}3.缩点相关问题我们这里只讨论一道缩点后的DAG的入度出度相关问题我们在统计完scc后只需要按照belong数组构建新的缩点后的DAG就可以具体构建方法为提前保留输入时的u和v存入数组之后判断u和v是否在同一scc,如果不在则说明belong[u]指向belong[v]同时也可以统计入度和出度然后进行DAG的操作即可此外还需要常常用到每个scc的大小可以在运行tarjan算法的时候就用一个数组统计以下面这道题为例https://www.luogu.com.cn/problem/P2341要想求明星的数量也就是说求其他所有的点都能到达他的点由于是有向图的连通问题考虑SCC我们不难发现缩点之后只要想所有点都指向自身只需要某个点为唯一出度为0的点就可以否则一定会有点未指向他也就不符合题意了示例代码如下#includebits/stdc.husingnamespacestd;usinglllonglong;constintMOD1e97;intn,m;vectorvectorintadj;vectorintdfn,low,belong;vectorvectorintSCC;intsccCnt0,cnt0;stackintst;voidtarjan(intu){dfn[u]low[u]cnt;st.push(u);for(intv:adj[u]){if(dfn[v]0){tarjan(v);low[u]min(low[u],low[v]);}elseif(belong[v]0){low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){sccCnt;vectorintScc;ints;do{sst.top();st.pop();belong[s]sccCnt;Scc.push_back(s);}while(s!u);SCC.push_back(Scc);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;vectorintu0(m),v0(m);adj.resize(n1);for(inti0;im;i){cinu0[i]v0[i];adj[u0[i]].push_back(v0[i]);}dfn.resize(n1,0);low.resize(n1,0);belong.resize(n1,0);for(inti1;in;i){if(dfn[i]0)tarjan(i);}vectorvectorintgscc(sccCnt1);vectorintout(sccCnt1,0);for(inti0;im;i){intubelong[u0[i]],vbelong[v0[i]];if(uv)continue;gscc[u].push_back(v);out[u];}intid0;for(inti1;isccCnt;i){if(out[i]0){if(!id)idi;else{cout0;return0;}}}coutSCC[id-1].size();return0;}此外缩点还有结合其他的DAG相关问题我们只需要当做普通DAG做就可以例如DAG上的拓扑序DP如下题所示这里不做讲解https://vjudge.net/problem/CSES-1686#authortranslator:1281311:zh4. 2-SAT的原理与求解过程2-SAT问题给定若干个变量以及若干个限定条件求出每个变量的值满足这些限定条件(1)原理①对于每个变量x都有且仅有两种取值x和非x②每条限制 形如x或y由逻辑学知识 能得出非x - y 以及 非y - x③任意两个变量x,y满足取反方向的对称性即如果有 x - y 一定有 非y - 非x④把每个变量的两种取值看作两个点每条关系都看做边就化为了一张图⑤对于这张图我们求解scc并进行缩点如果有同一变量的两种取值对应的两个点在同一个SCC里则说明两者矛盾无合法解⑥否则对于每个变量总是选择拓扑序靠后的点对应的取值如果拓扑序相同则任取⑦由于tarjan是dfs进行scc的分配的所以scc编号小的拓扑序大为了解释选择拓扑序靠后的点我们解释两个问题(1)为什么不选靠前的点例如x的两种取值a,b假设a的拓扑序靠前那么他一定可以到达b也就是a能推b可能出现x推出非x这种矛盾情况因此不成立(2)全部选靠后的点会不会出现内部矛盾例如x的两种取值a,b和y的两种取值c,d已知拓扑序a bc d,会不会出现b能推出c的情况呢假设a - b - … - c - d如果b出发发现确实能推出c看似确实是b,c符合但是如果b - c那么取反方向一定有 d - a显然这和原假设矛盾所以这种情况不可能出现(2)求解过程①对于第i个点的两种取值的编号由于总共有n个点我们设置true为ifalse为ni根据题意两边②对图使用tarjan算法求出强连通分量③首先判断belong[i]和belong[in]是否相等若存在相等输出无解并返回④否则比较每个i的belong[i]与belong[in]的大小关系选择拓扑序大也就是belong小的并根据题意输出取值即可5.2-SAT的示例代码例题链接#includebits/stdc.husingnamespacestd;usinglllonglong;constintMOD1e97;intn,m;vectorvectorintadj;vectorintdfn,low,belong;intsccCnt0,cnt0;stackintst;voidtarjan(intu){dfn[u]low[u]cnt;st.push(u);for(intv:adj[u]){if(dfn[v]0){tarjan(v);low[u]min(low[u],low[v]);}elseif(belong[v]0){low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){sccCnt;ints;do{sst.top();st.pop();belong[s]sccCnt;}while(s!u);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;adj.resize(n*21);// 注意点的编号是1-2ninti0,a,j0,b;for(inti0;im;i){cini0aj0b;// 表示xi0为a 或者 yj0为b(a,b 0/1)if(a0b0){// x1 y0 \ y1 x0adj[i0].push_back(j0n);adj[j0].push_back(i0n);}elseif(a0b1){// x1 y1 \ y0 x0adj[i0].push_back(j0);adj[j0n].push_back(i0n);}elseif(a1b1){// x0 y1 \ y0 x1adj[i0n].push_back(j0);adj[j0n].push_back(i0);}else{// x0 y0 \ y1 x1adj[i0n].push_back(j0n);adj[j0].push_back(i0);}}dfn.resize(n*21,0);low.resize(n*21,0);belong.resize(n*21,0);// 注意初始化为2n1for(inti1;in*2;i){// 注意是有2n个点if(dfn[i]0)tarjan(i);}// 求解强连通分量且无需额外计算大小/点的分布等// 判断是否无解for(inti1;in;i){if(belong[i]belong[in]){coutIMPOSSIBLE;return0;}}coutPOSSIBLE\n;// 有解根据两个取值SCC序号输出取值for(inti1;in;i){cout((belong[i]belong[in])?1:0) ;}return0;}我们这里不对2-SAT问题做更深一步的探究6.总结SCC 缩点是处理有向有环图的一把利器其核心思想可以概括为三步用Tarjan算法求出所有强连通分量每个分量内部的点都互相可达把每个 SCC 看成一个新节点缩点原图被缩成一张有向无环图DAG在DAG 上套用拓扑排序、DP 等手段高效求解原问题2‑SAT 则是 SCC 的经典应用场景通过将每个变量拆成“真”和“假”两个点并用“非 a - b”和“非 b - a”这两条蕴含关系建图矛盾当且仅当某个变量的两个点在同一个 SCC 中构造解时利用 Tarjan 算法产生的SCC 编号与拓扑序的关系选择拓扑序靠后的那个取值即可掌握了 Tarjan 与缩点的思想许多看似复杂的有向图问题都会被统一成简单的 DAG 模型。当然SCC 和 2‑SAT 还有更丰富的变化比如基环树、动态缩点等但本文给出的基础模板和常见应用已经能够解决大量题目,重要的是理解“互相可达”这一核心性质以及dfn与low如何巧妙地识别一个强连通分量从而进行迁移
