德赢vwin官网网址德赢vwin官网网址


vwin德赢手机客户端

浅谈Tarjan缩点(分析+模板)

昨天一看发现我的博客数量到100篇了,撒花✿✿ヽ(°▽°)ノ✿


根据标题我们也知道,想要在接下来的十分钟不浪费生命

读者需要先行学习Tarjan强联通分量

如果不会的话可以点击这里:https://www.cnblogs.com/WWHHTT/p/9744658.html

好的,现在我们就假设大家都知道了Tarjan,来看看如何利用Tarjan缩点

在学习如何写代码之前,我们必须要先弄明白什么是缩点

也就是定义

百度百科上并没有给出详细解释,我就来总结几句

缩点就是把一个有向图中的强联通分量转换成一个点

转换完之后的图是一个DAG(有向无环图)

通常用来解决图中具有传递性的问题(还有最大值和乘法原理)

我们来举个例子吧

上面这个图中,圆里的是编号,红色的是点的权值,箭头代表边的方向

这个图缩点之后是这样的

符号所表示的东西不变,原来的2,3,4变成了现在的2,原来的5是现在的3

 

是不是感觉没有多难,下面我来带大家看一下具体的实现流程

分为两步:

1.求出图中的强联同分量,并转化为点

2.将转化出来的新的点建成一个新的图

step1:

如何求出强联通分量就不多说了(不会的去看上面的链接)

每一种强联通分量会缩成一个点,这个店的编号我们就定为发现它的顺序,也就是染上的颜色

每一种颜色(一个强联通分量)对应一个点

但是要在中间加一个操作,用来计算一个联通分量的所缩成的点的点权(看注释)

 

void Tarjan(int x,int fa){//Tarjan模板 low[x]=dfn[x]=++tot; sta[++size]=x; book[x]=1; for(int e=head1[x];e;e=nxt1[e]){ if(!dfn[to1[e]]){ Tarjan(to1[e],x); low[x]=min(low[x],low[to1[e]]); } else if(book[to1[e]]) low[x]=min(low[x],dfn[to1[e]]); } if(dfn[x]==low[x]){ color[x]=++color_cnt; v2[color_cnt]=v[x]; book[x]=0; while(sta[size]!=x){ color[sta[size]]=color_cnt; book[sta[size]]=0; v2[color_cnt]+=v[sta[size]];//这个点的权值的计算,根据题目来确定 size--; } size--; } return ;}

 

 

step2:建图的边怎么练一直是个难点,首先可以确定的是因为原来的强连通分量已经变成一个个的点了

所以肯定无法照搬原图

但也不可能自创,所以需要判断,从原来的图上选择那些边

选边的原则是不能是一个强连通分量里的边

也就是说别的边都可以选

那么有的人就问了,缩完点之后不担心友谊重边吗

这很好处理,用邻接矩阵来存(不推荐),或者在之后的程序中标记都可以

特别提到,印的图要用一个新的邻接表来存

而且要连接的不是原来的点,而是两个点被染成的颜色

代码实现的话很简单,循环和dfs都可以,这里我们采用循环(代码量较小)

void change(){ for(int i=1;i<=n;i++){ for(int e=head1[i];e;e=nxt1[e]){ if(color[i]!=color[to1[e]]) add2(color[i],color[to1[e]]); } } return ;}

那么最后我们来总结一下代码

先给一组数据:(对应上面的图)5 5   //点的数量  边的数量

1 1 1 1 1   //点权

1 2  //边

2 3

3 4

4 2

2 5

输出:

3 //新的点的数量

1 3 1   //新的点的权值

下面给出代码:

#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>using namespace std;inline int min(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=="-") f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-"0"; return x*f;}inline void write(int x){ if(x<0) putchar("-"),x=-x; if(x>9) write(x/10); putchar(x%10+"0"); return ;}int n,m;int v[100006];int head1[100006],nxt1[200006],to1[200006];int total1=0;void add1(int x,int y){ total1++; to1[total1]=y; nxt1[total1]=head1[x]; head1[x]=total1; return ;}int dfn[100006],low[100006];int color[100006];int tot=0;int color_cnt=0;int book[100006];int sta[100006];int v2[100006];int size=0;void Tarjan(int x,int fa){//Tarjan模板 low[x]=dfn[x]=++tot; sta[++size]=x; book[x]=1; for(int e=head1[x];e;e=nxt1[e]){ if(!dfn[to1[e]]){ Tarjan(to1[e],x); low[x]=min(low[x],low[to1[e]]); } else if(book[to1[e]]) low[x]=min(low[x],dfn[to1[e]]); } if(dfn[x]==low[x]){ color[x]=++color_cnt; v2[color_cnt]=v[x]; book[x]=0; while(sta[size]!=x){ color[sta[size]]=color_cnt; book[sta[size]]=0; v2[color_cnt]+=v[sta[size]];//这个点的权值的计算,根据题目来确定 size--; } size--; } return ;}int head2[100006],nxt2[200006],to2[200006];int total2=0;void add2(int x,int y){ total2++; to2[total2]=y; nxt2[total2]=head2[x]; head2[x]=total2; return ;}void change(){ for(int i=1;i<=n;i++){ for(int e=head1[i];e;e=nxt1[e]){ if(color[i]!=color[to1[e]]){ add2(color[i],color[to1[e]]);//将两个点连边 } } } return ;}int main(){ n=rd(),m=rd(); for(int i=1;i<=n;i++) v[i]=rd();//得到点权 for(int i=1;i<=m;i++){ int x=rd(),y=rd(); add1(x,y);//有向边 } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,0); change(); int ans=0; printf("%d",color_cnt); for(int i=1;i<=color_cnt;i++){ printf("%d ",v2[i]); } return 0;}

 

欢迎阅读本文章: 何辉艳

vwin德赢唯一授权官网

vwin德赢手机客户端