缩点
一篇自认为可以讲懂缩点的文章.
什么是缩点?
简单的来说就是有向图上,把所有环缩成一个点的过程.
Q:有向图上的环是什么?
A:你想啊,环不就是能转圈吗?所以就是说如果有一群点可以互达,那么他们就是一个环上的啊.就跟下面这个0,2,3就是一个环啊,其实环里面的点就互为强连通分量.
Q:那是不是可能有很多重叠环?那怎么办?
A:是不是这种?
1,2,9是个环,1,3,5是个环,1,2,3,5,9还是个环,对吧.这样我们把它搞一个最大的环,如果两个点同时在这个最大的环上,那他们一定能互达吧.所以我们就放心求最大环就好了.
比如吧,这道题,显然如果有个环,那么我们可以认为一旦进了这个环,一定要取完环上的所有元素才最好对吗?
这时候我们就把所有的环缩成一个点就好了,权值就是所有环上的点的权值之和.然后在do sth.就好了.
缩点有什么用?
针对于有向图的DP或其他什么问题.
这类问题常常是这样的:给一个有向图,所有点不允许重复计算权值啥的,然后让你求什么条件下的什么值.就像文后给出的例题那样的就是了.
缩点之后得到的一定是一个DAG什么?你不知道DAG是有向无环图?,这样的话DP也就好确定状态转移啥的.当然还有其他用处,比较经典的就是DP.
怎么缩点
- 求出所有环
强连通分量 - 重构新图.
- Do sth you want.
1. 求强连通分量
Tarjan算法
据说这东西跑得快,但是可惜了,本巨弱不会啊其实是不想学了.
百度上有的是,可以找一篇学一下.
Kosaraju算法
算法流程
首先对于每个有向图G1,我们需要建一个反向图G2.
然后对G1进行第一遍DFS,因为并不保证图是连通的所以要DFS每个联通块.
第一遍DFS时用栈记录回溯的顺序,就是在遍历完所有子节点,轮到他return了就把它加到栈中然后return.
第二遍DFS以栈的顺序来进行,每一个可以被经过的点都是与当前的起点构成环(强连通分量)的点,将他们标记为出栈.并使用并查集来维护连通信息.
之后所有点都与它所在集合的点是同一个环(强联通分量)上的.
证明
我们按照算法描述的步骤往下走：
按照算法的结论，假设我们已经获得了一个逆后序排列，我们从中找两个元素，分别是V,W，W先出栈并且通过DFS找到了V。那么，V和W就是同一个联通分量的元素。到底是不是呢？
不管是不是，我们至少可以确定对于该有向图G，W有一条链接通往V，我们记作W->V。那么，对于该有向图的反向图G'，确定有链接V->W。
我们开始思考，在什么条件下，我们能够在反向图 G' 中获得V...W（即W先出栈）这样一个排列呢？要知道，我们刚刚确定了有链接V->W，所以逆后序排列中，应该是V排在W的前面，W...V这样啊？
所以在G'中，要么是我们之前提到的，在V->W的同时有W->V的链接；要么就是W和V之间没有任何联系，这样V的DFS结束之后，包含W的联通分量的DFS才开始遍历，才能造成W比V先出栈。
但是我们已经知道，V和W不是毫无关系的，确定有链接V->W，所以第二个可能不成立，所以必然存在一个W->V的链接，也就是W和V是互相联通的！
证明完毕。
--引自here
2.重构新图
既然每个联通块都用并查集来维护了,我们自然就能说并查集的代表元素当做一个强连通分量的编号.为了方便,我们并不需要对这些编号离散化.
原则:
两端点在同一个强连通分量里面的边不连.两端点不在同一个强连通分量里面连.
之后通过枚举边的起点和终点,然后重新建一个图就可以达到这个目的.
3.Do sth you want.
这个因题而定,一般为DAG上的动态规划问题,常常使用拓扑序确定其更新顺序,然后顺着更新就好了.
代码:
题目为Luogu模板题([模板]缩点)
#include<bits/stdc++.h>
using namespace std;
struct Side{
int to,net;
}s[3][100010];//0为正向原图,1为反向原图,2为重构图
int fr[3][10001],tails[3];//三个图对应三个东西
void add(int from,int to,int what){
s[what][++tails[what]].to=to;
s[what][tails[what]].net=fr[what][from];
fr[what][from]=tails[what];
}
int n,m,p1,p2,po,fa[10001],mo[10001];
bool vis[2][10001];
stack<int>ready;
int get_fa(int x){
if(fa[x]!=x)
fa[x]=get_fa(fa[x]);
return fa[x];
}
void dfs(int start,bool what){//两遍DFS我写到一起去了
vis[what][start]=1;
for(int lzh=fr[what][start];lzh;lzh=s[what][lzh].net){
if(!vis[what][s[what][lzh].to]){//必须是没访问过才行
if(what)//1的情况就是第二次DFS,需要更新并查集
fa[s[what][lzh].to]=get_fa(start);
dfs(s[what][lzh].to,what);
}
}
if(!what)
ready.push(start);//0的情况需要用栈保存回溯顺序.
}
void suo(){
for(int i=1;i<=n;++i)
if(!vis[0][i])//一遍DFS每个联通块
dfs(i,0);
while(!ready.empty()){
po=ready.top();//按栈的顺序来
ready.pop();
if(!vis[1][po])
dfs(po,1);
}
}
int cnt[10001];//记录入度,方便拓扑排序
void Build_Chart(){
for(int i=1;i<=n;++i){
for(int lzh=fr[0][i];lzh;lzh=s[0][lzh].net){
if(get_fa(i)==get_fa(s[0][lzh].to))//同一个联通块
continue;
add(get_fa(i),get_fa(s[0][lzh].to),2);//重构图记为2,正向边
++cnt[get_fa(s[0][lzh].to)];
}
}
}
queue<int>far;int dp[10001],ans;
int Far_Far_Far(){//简单的DP我就不讲了
for(int i=1;i<=n;i++)
if(get_fa(i)!=i)
mo[get_fa(i)]+=mo[i];
for(int i=1;i<=n;++i)
if(get_fa(i)==i){
dp[i]=mo[i];
ans=max(ans,dp[i]);
if(!cnt[i])
far.push(i);
}
while(!far.empty()){
int nowdo=far.front();
far.pop();
for(int lzh=fr[2][nowdo];lzh;lzh=s[2][lzh].net){
dp[s[2][lzh].to]=max(dp[nowdo]+mo[s[2][lzh].to],dp[s[2][lzh].to]);
ans=max(ans,dp[s[2][lzh].to]);
if((--cnt[s[2][lzh].to])==0)
far.push(s[2][lzh].to);
}
}
return ans;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&mo[i]),
fa[i]=i;//初始话并查集
for(int i=1;i<=m;++i){
scanf("%d %d",&p1,&p2);
add(p1,p2,0);//正向图
add(p2,p1,1);//反向图
}
suo();//1.缩点
Build_Chart();//2.重构图
cout<<Far_Far_Far();//Do sth.
return 0;
}一些例题
模板题就叫 缩点 我就不放了.
- https://www.luogu.org/problemnew/show/P1726
- https://www.luogu.org/problemnew/show/P2341
- https://www.luogu.org/problemnew/show/P2746
- https://www.luogu.org/problemnew/show/P3119
前三题近乎模板题,后面一题难度有所提高.