【图论】Tarjan 缩点：解决有向图中环的问题

题目链接P3387 【模板】缩点 / 强连通分量 - 洛谷有向无环图DAG具有很多很好用的性质因为没有环而且有向无环图必定有一个点是入度为 0 也必定有个点是出度为 0 所以非常适合拓扑排序也因为没有环所以比如找最优路径或是路径方案数的时候可用动态规划 DP 很快速就能解决。但有些情况下可能给到的并不是一个有向无环图而只是一个有向图。里面有可能存在环也就无法利用刚刚所提到的性质了。可如果可以把环去掉把有向图转化成一个有向无环图那我们就能利用有向无环图的性质去解题了。而 Tarjan 缩点就是把有向图转变成有向无环图的方法。如洛谷 P3387 题目我们很快其实就能发现要找这个权值最大的路径第一想法当然是进行动态规划 DP 。但是题目提供的图并不是一个有向无环图而是一个有向图是可能有环的。而一旦有环在进行 DP 的过程就很麻烦还可能死循环。在了解 Tarjan 算法之前先看看环是如何导致 DP 难以进行的。由于环的存在很可能在图上走的时候就会突然回到之前走过的节点。当然可以标记每个点是否去过但是这样一来还有问题是无法找到一个结束循环的地方。因为不能一概而论的碰到走过的节点就不继续走下去也不能一直走下去。但是可以发现一个关键点是由于题目说“可以重复走但是走过的节点只算一次”那也就是说碰到环的话那肯定得走完一圈回来才值。对于图上的一些可以互相到达的节点的集合称为强连通分量SCC。一个环或者多个环嵌套一起都算一个强连通分量因为他们任意节点都可以相互到达而一个孤立的节点是一个特殊的强连通分量。更进一步可以发现其实在图上对于任意一个强连通分量只要碰到它们内部任意一个节点那我肯定得走完全部节点得到全部权值才是赚的。所以说最优的策略其实就是到达一个强连通分量就把内部所有节点的权值都加上那这个强连通分量就有点类似可以浓缩成一个“节点”。如下图容易发现图中 2 3 4 5 6 组成的环就是一个强连通分量而 Tarjan 缩点的策略就是把这一整个强连通分量如图示缩成一个点这个点会拥有原本强连通分量的所有性质比如仍然可以到达 7 8 这两个点且一整个点的权值应该是 2 3 4 5 6 的权值和。缩点方法首先给大家看一个简单的模板再做其他解释。#include bits/stdc.h using namespace std; #define int long long const int maxn2e510; vectorvectorint g(maxn);//原有向图 int dfn[maxn];//指节点i的编号 int low[maxn];//指节点i最多能回到之前的哪个节点也可以说是最早出现的时间戳 bool st[maxn];//用于标注当前节点是否已入栈 stackint sk;//已入栈的节点也代表着之前已经到达过了 setpairint,int s;//用于去重建立新图DAG int cnt;//用于分配编号 int scc[maxn];//scc[i]是i节点在新的DAG图中的对应缩点编号 vectorvectorint dag(maxn);//新图DAG void dfs(int p){ dfn[p]low[p]cnt;//先分配一个编号 st[p]true; sk.push(p);//标注true并入栈 //遍历当前节点的所有出边 for(int i:g[p]){ //如果dfn发现是0说明没来过这个点先进行dfs再更新low值取最小值是为了找能到达最早的节点 //如果这个点之前走过了而发现它还在栈内节点p可以回到这个i点可能形成环直接更新low值 if(!dfn[i]){ dfs(i); low[p]min(low[p],low[i]); }else if(st[i]){ low[p]min(low[p],dfn[i]); } } //如果dfn和low值相等说明这个p节点是缩点的根节点 if(dfn[p]low[p]){ //此时栈内的节点一直到p节点都是同一缩点内的一直从栈内取出节点即可 while(true){ int tsk.top(); sk.pop(); st[t]false;//取出后pop并标记变为false scc[t]p;//标记上缩点的编号 if(tp) break;//到p节点说明当前强连通分量已经遍历完了break } } } void solve(){ int n,m; cinnm; for(int i1;im;i){ int u,v; cinuv; g[u].push_back(v); } //遍历所有点进行缩点 for(int i1;in;i){ if(!dfn[i]) dfs(i); } //找出有效的新图DAG的边去重 for(int i1;in;i){ for(int j:g[i]){ if(scc[i]scc[j]) continue;//scc相等说明同在一个缩点内无效边 s.insert({scc[i],scc[j]}); } } //建立新图 for(const auto i:s){ dag[i.first].push_back(i.second); } } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int t1; //cint; while(t--) solve(); return 0; }注释交代其实已经比较清晰了通过 dfs 的搜索dfn 和 low 来判断当前点是否属于一个 scc 根节点来进行缩点而从 sk 栈中找到属于同一个缩点的节点。整体而言并不算特别复杂。我个人而言经常就在把节点从栈内取出后忘记标记 st 为 false 了其他基本都不会出很大问题。但这里我用的 set 去重这个开销还是稍微大了一点也可以转用 unique 去重。vectorpairint,int s; for(int i1;in;i){ for(int j:g[i]){ if(scc[i]scc[j]) continue;//scc相等说明同在一个缩点内无效边 s.push_back({scc[i],scc[j]}); } } sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end());解题方法知道了缩点的方法后解决这个 P3387 就不算很困难了因为缩点后就是有向无环图 DAG 进行 DP 非常简单。而我们只需要对原本的缩点模板加入一点修改即可修改处我会标出。#include bits/stdc.h using namespace std; #define int long long const int maxn2e510; vectorvectorint g(maxn);//原有向图 int dfn[maxn];//指节点i的编号 int low[maxn];//指节点i最多能回到之前的哪个节点也可以说是最早出现的时间戳 bool st[maxn];//用于标注当前节点是否已入栈 stackint sk;//已入栈的节点也代表着之前已经到达过了 setpairint,int s;//用于去重建立新图DAG int cnt;//用于分配编号 int scc[maxn];//scc[i]是i节点在新的DAG图中的对应缩点编号 vectorvectorint dag(maxn);//新图DAG int arr[maxn];//原图权值 int sum[maxn];//累加缩点后的权值 void dfs(int p){ dfn[p]low[p]cnt;//先分配一个编号 st[p]true; sk.push(p);//标注true并入栈 //遍历当前节点的所有出边 for(int i:g[p]){ //如果dfn发现是0说明没来过这个点先进行dfs再更新low值取最小值是为了找能到达最早的节点 //如果这个点之前走过了而发现它还在栈内节点p可以回到这个i点可能形成环直接更新low值 if(!dfn[i]){ dfs(i); low[p]min(low[p],low[i]); }else if(st[i]){ low[p]min(low[p],dfn[i]); } } //如果dfn和low值相等说明这个p节点是缩点的根节点 if(dfn[p]low[p]){ //此时栈内的节点一直到p节点都是同一缩点内的一直从栈内取出节点即可 while(true){ int tsk.top(); sk.pop(); st[t]false;//取出后pop并标记变为false scc[t]p;//标记上缩点的编号 //// sum[p]arr[t];//新增为缩点累加权值 //// if(tp) break;//到p节点说明当前强连通分量已经遍历完了break } } } //dp逻辑 int dp[maxn]; int dpdfs(int p){ if(dp[p]!-1) return dp[p]; int ans0; for(int i:dag[p]){ ansmax(ans,dpdfs(i)); } dp[p]anssum[p]; return dp[p]; } void solve(){ int n,m; cinnm; for(int i1;in;i) cinarr[i]; for(int i1;im;i){ int u,v; cinuv; g[u].push_back(v); } //遍历所有点进行缩点 for(int i1;in;i){ if(!dfn[i]) dfs(i); } //找出有效的新图DAG的边去重 for(int i1;in;i){ for(int j:g[i]){ if(scc[i]scc[j]) continue;//scc相等说明同在一个缩点内无效边 s.insert({scc[i],scc[j]}); } } //建立新图 for(const auto i:s){ dag[i.first].push_back(i.second); } memset(dp,-1,sizeof(dp));//初始化 int ans0; for(int i1;in;i){ ansmax(ans,dpdfs(scc[i])); } coutans\n; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int t1; //cint; while(t--) solve(); return 0; }