Tarjan全家桶系列--强联通分量

强联通分量(SCC)

有向图中的一个​​极大子图​，其中任意两个节点u和v都​​互相可达​（即存在u→v和v→u的路径），则这个子图为一个强联通分量
Tarjan 算法基于深度优先搜索（DFS），利用 DFS 序dfn和low链 来判断一个节点是否是某个强连通分量的“根”（即最早被访问的节点）。

基本定义：

强连通分量（SCC）：有向图中，任意两个节点 u, v 互相可达的最大子图。
dfn[u]：节点 u 被 DFS 第一次访问的时间戳（DFS 序）。
low[u]：从 u 出发，通过若干条边（可以走树边、后向边、横叉边），能到达的所有节点中 最小的 dfn 值。
换句话说：low[u] = min{ dfn[v] | v 从 u 出发可达 }

关键性质：

如果在 DFS 回溯时发现low[u] == dfn[u]，说明 u 是当前 SCC 的“根”。
因为从 u 出发无法回到比 u 更早访问的节点。
此时，从栈顶到 u 的所有节点构成一个 SCC。

栈的作用：

DFS 过程中，将访问的节点压入栈。
当找到一个 SCC 的根时，从栈中弹出直到 u，这些节点就属于同一个 SCC。

模板

说明：void Run(int _n,const vector<int>adj[])为传入点的数量，vector邻接表数组，运行求出所有强联通分量 。·vector<int> Get()为获取scc数组，即scc[i]为i点属于的强连通分量编号

template<intN>structSCC{vector<int>scc;vector<int>stk;intdfn[N],low[N];constvector<int>*adj;intn,clk,tot;//tot:scc数量voiddfs(intu){++clk;dfn[u]=low[u]=clk;stk.push_back(u);for(intto:adj[u]){if(dfn[to]==-1){dfs(to);low[u]=min(low[u],low[to]);}elseif(scc[to]==-1)low[u]=min(low[u],dfn[to]);}if(low[u]==dfn[u]){intv=-1;++tot;do{v=stk.back();stk.pop_back();scc[v]=tot;}while(v!=u);}}voidRun(int_n,constvector<int>adj[]){n=_n;clk=tot=0;stk.clear();fill(low,low+3+n,-1);fill(dfn,dfn+3+n,-1);scc.assign(n+3,-1);this->adj=adj;for(inti=1;i<=n;++i)if(scc[i]==-1)dfs(i);}vector<int>Get(){returnscc;}};

使用示例

template<intN>structSCC{vector<int>scc;vector<int>stk;intdfn[N],low[N];constvector<int>*adj;intn,clk,tot;//tot:scc数量voiddfs(intu){++clk;dfn[u]=low[u]=clk;stk.push_back(u);for(intto:adj[u]){if(dfn[to]==-1){dfs(to);low[u]=min(low[u],low[to]);}elseif(scc[to]==-1)low[u]=min(low[u],dfn[to]);}if(low[u]==dfn[u]){intv=-1;++tot;do{v=stk.back();stk.pop_back();scc[v]=tot;}while(v!=u);}}voidRun(int_n,constvector<int>adj[]){n=_n;clk=tot=0;stk.clear();fill(low,low+1+n,-1);fill(dfn,dfn+1+n,-1);scc.assign(n+3,-1);this->adj=adj;for(inti=1;i<=n;++i)if(scc[i]==-1)dfs(i);}vector<int>Get(){returnscc;}};constintmaxn=2*1e5+20;SCC<maxn>T;vector<int>e[maxn];intmain(){intn,m;//n个点，m条边for(inti=1;i<=m;++i){//输入m条边intu,v;cin>>u>>v;e[u].push_back(v);}T.Run(n,e);//跑tarjanvector<int>scc=T.Get();//获取scc数组，scc[i]=i点属于的强连通分量编号