在算法题中，我们时常会遇到有向图上的连通性问题，比如求从起点到终点最多能收集多少硬币，或者判断整张图是否任意两点都互相可达。对于无环的有向图（DAG），我们可以轻松地用拓扑排序进行 DP，时间复杂度仅为 O(n+m)。然而，一旦图中出现了环，情况就变得棘手：环的存在导致无法直接拓扑排序，朴素的 DFS/BFS 很难处理环中的最优决策。那么，有没有一种方法，能够将有环图“拍平”，使其变成 DAG，从而继续享受拓扑排序的便利呢？答案是肯定的。我们可以引入一种设计巧妙的图论组合：强连通分量（SCC）缩点，配合Tarjan 算法，它可以在 O(n+m) 的线性时间内完成缩点，并且还能自然推广到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-b，b-c，c-d都为树边,d-b为回边，若从d经过了efg，确定了efg为一个SCC,则之后回溯到c，c-h为树边，h-a为回边，h-g为弃边
②dfn[u]:节点u分配的dfn序号
③low[u]：从u及其子树上点最多走一条回边到达最上面（即序号最小）的点的dfn序号
如dfn[a] = 1;
则b通过b-h和回边h-a到a，dfn[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 ）
示例代码如下
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintMOD=1e9+7;intn,m;vector<vector<int>>adj;vector<int>dfn,low,belong;intsccCnt=0,cnt=0;stack<int>st;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{s=st.top();st.pop();belong[s]=sccCnt;}while(s!=u);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);intu0,v0;cin>>n>>m;adj.resize(n+1);for(inti=0;i<m;i++){cin>>u0>>v0;adj[u0].push_back(v0);}dfn.resize(n+1,0);low.resize(n+1,0);belong.resize(n+1,0);for(inti=1;i<=n;i++){if(dfn[i]==0)tarjan(i);}cout<<sccCnt<<"\n";vector<bool>flag(n+1,false);for(inti=1;i<=n;i++){if(!flag[i]){intscc=belong[i];for(intj=1;j<=n;j++){if(belong[j]==scc){cout<<j<<" ";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的点就可以，否则，一定会有点未指向他，也就不符合题意了
示例代码如下：
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintMOD=1e9+7;intn,m;vector<vector<int>>adj;vector<int>dfn,low,belong;vector<vector<int>>SCC;intsccCnt=0,cnt=0;stack<int>st;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++;vector<int>Scc;ints;do{s=st.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);cin>>n>>m;vector<int>u0(m),v0(m);adj.resize(n+1);for(inti=0;i<m;i++){cin>>u0[i]>>v0[i];adj[u0[i]].push_back(v0[i]);}dfn.resize(n+1,0);low.resize(n+1,0);belong.resize(n+1,0);for(inti=1;i<=n;i++){if(dfn[i]==0)tarjan(i);}vector<vector<int>>gscc(sccCnt+1);vector<int>out(sccCnt+1,0);for(inti=0;i<m;i++){intu=belong[u0[i]],v=belong[v0[i]];if(u==v)continue;gscc[u].push_back(v);out[u]++;}intid=0;for(inti=1;i<=sccCnt;i++){if(out[i]==0){if(!id)id=i;else{cout<<0;return0;}}}cout<<SCC[id-1].size();return0;}此外，缩点还有结合其他的DAG相关问题，我们只需要当做普通DAG做就可以，例如DAG上的拓扑序DP，如下题所示，这里不做讲解
https://vjudge.net/problem/CSES-1686#author=translator:1281311:zh
4. 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 < b，c < d,会不会出现b能推出c的情况呢？
假设a -> b -> … -> c -> d，如果b出发，发现确实能推出c，看似确实是b,c符合，但是如果b -> c，那么取反方向，一定有 d -> a，显然这和原假设矛盾，所以这种情况不可能出现
(2)求解过程
①对于第i个点的两种取值的编号，由于总共有n个点，我们设置true为i，false为n+i，根据题意两边
②对图使用tarjan算法，求出强连通分量
③首先判断belong[i]和belong[i+n]是否相等，若存在相等，输出无解并返回
④否则，比较每个i的belong[i]与belong[i+n]的大小关系，选择拓扑序大也就是belong小！！！的并根据题意输出取值即可
5.2-SAT的示例代码
例题链接：
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintMOD=1e9+7;intn,m;vector<vector<int>>adj;vector<int>dfn,low,belong;intsccCnt=0,cnt=0;stack<int>st;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{s=st.top();st.pop();belong[s]=sccCnt;}while(s!=u);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;adj.resize(n*2+1);// 注意点的编号是1-2ninti0,a,j0,b;for(inti=0;i<m;i++){cin>>i0>>a>>j0>>b;// 表示xi0为a 或者 yj0为b(a,b == 0/1)if(a==0&&b==0){// x1 y0 \ y1 x0adj[i0].push_back(j0+n);adj[j0].push_back(i0+n);}elseif(a==0&&b==1){// x1 y1 \ y0 x0adj[i0].push_back(j0);adj[j0+n].push_back(i0+n);}elseif(a==1&&b==1){// x0 y1 \ y0 x1adj[i0+n].push_back(j0);adj[j0+n].push_back(i0);}else{// x0 y0 \ y1 x1adj[i0+n].push_back(j0+n);adj[j0].push_back(i0);}}dfn.resize(n*2+1,0);low.resize(n*2+1,0);belong.resize(n*2+1,0);// 注意初始化为2n+1for(inti=1;i<=n*2;i++){// 注意是有2n个点if(dfn[i]==0)tarjan(i);}// 求解强连通分量，且无需额外计算大小/点的分布等// 判断是否无解for(inti=1;i<=n;i++){if(belong[i]==belong[i+n]){cout<<"IMPOSSIBLE";return0;}}cout<<"POSSIBLE"<<"\n";// 有解，根据两个取值SCC序号输出取值for(inti=1;i<=n;i++){cout<<((belong[i]<belong[i+n])?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如何巧妙地识别一个强连通分量，从而进行迁移
