强连通分量&2-SAT&双联通分量&Dorminator Tree
orz hhw
posted @ 2015年5月10日 16:46
in 算法学习
with tags
模板 Tarjan 2-SAT bzoj 算法学习 联通分量 Dorminator Tree
, 3202 阅读
这两天把tarjan算法好好理解学习了下，应该大致搞懂了
一、强连通分量
强连通分量大概就是一个子图中每个点都可以到达其他所有的点，这就是一个强连通分量，可以把强连通分量中的点缩成一个点解决问题
tarjan算法模板
void tarjan(int x){
int now=0;
dfn[x]=low[x]=++time;
stack[++top]=x;
instack[x]=1;
for(int i=first[x];i;i=next[i]){
int y=last[i];
if(!dfn[y]){tarjan(y);if(low[y]<low[x])low[x]=low[y];}
else if(instack[y]&&dfn[y]<low[x])low[x]=dfn[y];
}
if(low[x]==dfn[x]){
scnt++;
while(now!=x){
now=stack[top];top--;
instack[now]=0;
belong[now]=scnt;
}
}
}
缩点模板
void rebuild(){
for(int x=1;x<=n;x++){
for(int i=first[x];i;i=next[i])
if(belong[x]!=belong[last[i]]&&!mark[belong[last[i]]])
mark[belong[last[i]]]=1,insert2(belong[x],belong[last[i]]);
for(int i=first[x];i;i=next[i])
if(belong[x]!=belong[last[i]])
mark[belong[last[i]]]=0;
}
}
BZOJ1179：缩点后求点权最长路
#include<cstdio>
#define N 555555
using namespace std;
int n,m,i,j,x,y,ans,top,tot,tot2,cnt,scnt,time,S,P,c[N],next[N],last[N],first[N],last2[N],next2[N],first2[N],belong[N],dfn[N],low[N],val[N],dis[N],stack[N],q[N<<4];
bool v[N],instack[N];
void insert(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void ins(int x,int y){last2[++tot2]=y;next2[tot2]=first2[x];first2[x]=tot2;}
void tarjan(int x){
int now=0;
dfn[x]=low[x]=++time;
stack[++top]=x;
instack[x]=1;
for(int i=first[x];i;i=next[i]){
int y=last[i];
if(!dfn[y]){tarjan(y);if(low[y]<low[x])low[x]=low[y];}
else if(instack[y]&&dfn[y]<low[x])low[x]=dfn[y];
}
if(low[x]==dfn[x]){
scnt++;
while(now!=x){
now=stack[top];top--;
instack[now]=0;
belong[now]=scnt;
val[scnt]+=c[now];
}
}
}
void rebuild(){
for(i=1;i<=n;i++)
for(j=first[i];j;j=next[j])
if(belong[i]!=belong[last[j]])
ins(belong[i],belong[last[j]]);
}
void spfa(){
int head=0,tail=1;
q[1]=belong[S];v[belong[S]]=1;dis[belong[S]]=val[belong[S]];
while(head!=tail)
for(i=first2[x=q[++head]],v[x]=0;i;i=next2[i])
if(dis[x]+val[y=last2[i]]>dis[y]){
dis[y]=dis[x]+val[y];
if(!v[y])v[q[++tail]=y]=1;
}
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),insert(x,y);
for(i=1;i<=n;i++)scanf("%d",&c[i]);
for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
scanf("%d%d",&S,&P);
rebuild();
spfa();
for(i=1;i<=P;i++){
scanf("%d",&x);
if(dis[belong[x]]>ans)ans=dis[belong[x]];
}
printf("%d",ans);
}
BZOJ2438：缩点后求入度为0的联通块个数ans，若存在只有一个点的连通块，它无出边或出边指向的点均能被其它点到达则ans--
#include<cstdio>
#define M 333333
#define N 111111
using namespace std;
int n,m,i,j,x,y,scnt,tot,tot2,top,ans,time,now,last[M],next[M],last2[M],next2[M],first[N],first2[N],d[N],dfn[N],low[N],num[N],belong[N],stack[N];
bool instack[N],mark[N];
void insert(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void insert2(int x,int y){last2[++tot2]=y;next2[tot2]=first2[x];first2[x]=tot2;d[y]++;}
void tarjan(int x){
dfn[x]=low[x]=++time;
instack[x]=1;stack[++top]=x;
for(int i=first[x];i;i=next[i]){
int y=last[i];
if(!dfn[y]){
tarjan(y);
if(low[y]<low[x])low[x]=low[y];
}else if(instack[y]&&dfn[y]<low[x])low[x]=dfn[y];
}
if(dfn[x]==low[x]){
scnt++;now=0;
while(now!=x){
now=stack[top];top--;
instack[now]=0;
belong[now]=scnt;
num[scnt]++;
}
}
}
void rebuild(){
for(int x=1;x<=n;x++){
for(int i=first[x];i;i=next[i])
if(belong[x]!=belong[last[i]]&&!mark[belong[last[i]]])
mark[belong[last[i]]]=1,insert2(belong[x],belong[last[i]]);
for(int i=first[x];i;i=next[i])
if(belong[x]!=belong[last[i]])
mark[belong[last[i]]]=0;
}
}
bool judge(int x){
if(d[x]||num[x]!=1)return 0;
for(int i=first2[x];i;i=next2[i])if(d[last2[i]]==1)return 0;
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
insert(x,y);
}
for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
rebuild();
for(i=1;i<=scnt;i++)if(!d[i])ans++;
for(i=1;i<=scnt;i++)if(judge(i)){ans--;break;}
printf("%.6lf",(double)(n-ans)/n);
}
BZOJ1093 缩点+树上DP
#include<cstdio>
#define N 111111
#define M 1111111
using namespace std;
int n,m,MOD,x,y,i,mav,ans,tot,tot2,top,scnt,now,head,tail,time,dfn[N],low[N],first[N],first2[N],belong[N],num[N],f[N],g[N],r[N],stack[N],vis[N],last[M],next[M],last2[M],next2[M],q[M];
bool instack[N],mark[N];
void insert(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void insert2(int x,int y){last2[++tot2]=y;next2[tot2]=first2[x];first2[x]=tot2;r[y]++;}
void tarjan(int x){
dfn[x]=low[x]=++time;
instack[x]=1;
stack[++top]=x;
for(int i=first[x];i;i=next[i]){
int y=last[i];
if(!dfn[y]){
tarjan(y);
if(low[y]<low[x])low[x]=low[y];
}else if(instack[y]&&dfn[y]<low[x])low[x]=dfn[y];
}
if(dfn[x]==low[x]){
scnt++;now=0;
while(now!=x){
now=stack[top];top--;
belong[now]=scnt;
instack[now]=0;
num[scnt]++;
}
}
}
void rebuild(){
for(int x=1;x<=n;x++){
for(i=first[x];i;i=next[i])
if(belong[y=last[i]]!=belong[x]&&!mark[belong[y]])mark[belong[y]]=1,insert2(belong[x],belong[y]);
for(i=first[x];i;i=next[i])
if(belong[y=last[i]]!=belong[x])mark[belong[y]]=0;
}
}
void dp(){
for(i=1;i<=scnt;i++){
if(!r[i])q[++tail]=i;
f[i]=num[i];g[i]=1;
}
while(head!=tail){
for(i=first2[x=q[++head]];i;i=next2[i]){
int y=last2[i];
if(0==--r[y])q[++tail]=y;
if(vis[y]!=x){
if(f[x]+num[y]>f[y])f[y]=f[x]+num[y],g[y]=g[x];
else if(f[x]+num[y]==f[y])g[y]=(g[x]+g[y])%MOD;
vis[y]=x;
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&MOD);
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),insert(x,y);
for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
rebuild();
dp();
for(i=1;i<=scnt;i++)if(f[i]>mav)mav=f[i],ans=g[i];else if(f[i]==mav)ans=(ans+g[i])%MOD;
printf("%d\n%d",mav,ans);
}
BZOJ1194 BFS判断建边，tarjan+DP得到答案
#include<bits/stdc++.h>
using namespace std;bool is[55],v[55][55];int S,n,i,j,h,t,x,y,m,id,tot,scc,ans,d[55],q[55],du[55],dfn[55],low[55],e[55][55],c[55][55][2],fir[55],Fir[55],bl[55],sz[55],ne[5555],la[5555],X[5555],Y[5555];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void Ins(int x,int y){la[++tot]=y;ne[tot]=Fir[x];Fir[x]=tot;du[y]++;}
bool ok(int S,int T){
int i,h=0,t=1,F,G,x,y;
for(memset(v,0,sizeof(v)),h=0,v[1][1]=1,X[1]=1,Y[1]=1;h^t;){
x=X[++h];y=Y[h];if(e[S][x]&&!e[T][y])return 0;
for(i=0;i<2;i++)if(!v[F=c[S][x][i]][G=c[T][y][i]])X[++t]=F,Y[t]=G,v[F][G]=1;
}return 1;
}
void tj(int x){
q[++t]=x;is[x]=1;dfn[x]=low[x]=++id;int i,y,o=0;
for(i=fir[x],y;i;i=ne[i])if(!dfn[y=la[i]])tj(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x])for(scc++;o!=x;is[o]=0)sz[bl[o=q[t--]]=scc]++;
}
int main(){
for(scanf("%d",&S),i=1;i<=S;i++){
for(scanf("%d%d",&n,&m);m--;e[i][x]=1)scanf("%d",&x),x++;
for(j=1;j<=n;j++)scanf("%d%d",&c[i][j][0],&c[i][j][1]),c[i][j][0]++,c[i][j][1]++;
}
for(i=1;i<=S;i++)for(j=1;j<=S;j++)if(ok(i,j)&&i!=j)ins(i,j);
for(i=1;i<=S;i++)if(!dfn[i])tj(i);
for(x=1;x<=S;x++)for(i=fir[x];i;i=ne[i])if(bl[x]!=bl[la[i]])Ins(bl[x],bl[la[i]]);
for(t=0,i=1;i<=scc;i++)if(!du[i])q[++t]=i;
for(;h^t;)for(d[x=q[++h]]+=sz[x],ans=max(ans,d[x]),i=Fir[x];i;i=ne[i])if(d[y=la[i]]=max(d[y],d[x]),!--du[y])q[++t]=y;
printf("%d",ans);
}
然后似乎dfn[u]<=low[v]这个u点就是割点，改成小于号这条边就是割边、不过没发现有什么用
二、2-SAT
今天看了下2-SAT，竟然一下就懂了，大概就是有一些约束条件，如果选A就必须选B就从A向B连一条边，然后如果两个只能选一个的条件在同一个强连通分量重就不合法，否则可以通过拓扑排序求出一种可行方案
BZOJ1823满汉全席 2-SAT裸题
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 222
#define M 2222
using namespace std;
#define CL(a) memset(a,0,sizeof(a))
int T,i,n,m,p,x,y,mxh,mjy,tot,top,scnt,sz,now,belong[N],dfn[N],low[N],stack[N],fir[N],ne[M],la[M];
bool flag,is[N];char c,ch;
void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';x*=2;
}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int get(){
for(c=getchar();c!='m'&&c!='h';c=getchar());
read(p);
return c=='m'?p:p-1;
}
void tarjan(int x){
dfn[x]=low[x]=++sz;
is[x]=1;stack[++top]=x;
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
else if(is[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
scnt++;now=0;
while(now!=x){
now=stack[top--];
is[now]=0;
belong[now]=scnt;
}
}
}
int main(){
scanf("%d",&T);
while(T--){
CL(dfn);CL(low);CL(fir);tot=scnt=sz=top=0;flag=1;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
x=get();y=get();
if(x&1)mxh=x++;else mxh=x--;
if(y&1)mjy=y++;else mjy=y--;
ins(mxh,y);ins(mjy,x);
}
for(i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
for(i=1;i<=n;i++)if(belong[i*2]==belong[i*2-1]){flag=0;break;}
if(flag)puts("GOOD");else puts("BAD");
}
}
UER#6寻找罪犯 2-SAT建图的优化，建立前缀/后缀是否是罪犯节点，点数6N，边数12N。输出方案判bl即可。
#include<bits/stdc++.h>
#define N 600100
using namespace std;bool is[N],ff,vs[N];struct P{int x,y;};vector<P>V[N];
int n,m,i,j,l,x,y,z,o,X,Y,ds,id,cnt,tot,top,w,E[N],st[N],low[N],dfn[N],fir[N],ne[N*13],la[N*13],bl[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void tj(int x){
low[x]=dfn[x]=++id;is[x]=1;st[++top]=x;int y,i,o=0;
for(i=fir[x];i;i=ne[i])if(!dfn[y=la[i]])tj(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x])for(cnt++;o!=x;o=st[top--],bl[o]=cnt,is[o]=0);
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),V[x].push_back(P{y,z});
for(ds=n*2,x=1;x<=n;x++){
for(l=V[x].size(),i=0;i<l;i++)if(V[x][i].y)ins(x,V[x][i].x);else ins(x,V[x][i].x+n);
for(i=1;i<l;i++)ins(ds+i,ds+i+1),ins(ds+i+l*2+1,ds+i+l*2),ins(ds+i,ds+i+l*3+1),ins(ds+i+l*3+1,ds+i),ins(ds+i+l,ds+i+l*2+1),ins(ds+i+l*2+1,ds+i+l);
for(i=0;i<l;i++)if(X=V[x][i].x,Y=X+n,V[x][i].y)ins(Y,x+n),ins(Y,ds+i+1),ins(Y,ds+i+l*2+1),ins(ds+i+l+1,X),ins(ds+i+l*3+1,X);else ins(X,x+n),ins(X,ds+i+1),ins(X,ds+i+l*2+1),ins(ds+i+l+1,Y),ins(ds+i+l*3+1,Y);
ds+=V[x].size()*4;
}
for(i=1;i<=ds;i++)if(!dfn[i])tj(i);ff=0;
for(i=1;i<=n;i++)if(bl[i]==bl[i+n])ff=1;
if(ff)return puts("Impossible"),0;
for(i=1;i<=n;i++)if(bl[i]>=bl[i+n])E[++w]=i;
for(printf("%d\n",w),i=1;i<=w;i++)printf("%d ",E[i]);
}
三、双联通分量
今天做到一道题要用到这个就看了下，大概就是子图中所有点任意删去一点还互相联通，则这个子图是点双联通的，如果删去任意一边互相连通，则这个子图是边双联通的，双联通分量可以解决一些无向图求割点、割边的问题
#include<cstdio>
#include<algorithm>
#define N 202000
#define M 2002000
using namespace std;
int n,m,i,x,y,tot,time,top,rt,sz,scc,tp,now,st[N],bl[N],cut[N],low[N],dfn[N],fir[N],ans[M],la[M],ne[M];bool ok[M],is[N];
void add(int x,int y){
for(int i=fir[x];i;i=ne[i])if(la[i]==y){if(i)ok[i]=1;return;}
la[++tot]=y;ne[tot]=fir[x];ok[tot]=0;fir[x]=tot;
}
void ins(int x,int y){add(x,y);add(y,x);}
int dfs(int x,int fa){
dfn[x]=low[x]=++time;is[x]=1;st[++tp]=x;
int i,y,cd=0;
for(i=fir[x];i;i=ne[i]){
y=la[i];
if(!dfn[y]){
dfs(y,x);cd++;
if(x!=rt&&dfn[x]<=low[y])cut[++sz]=x;
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x]&&!ok[i])ans[++top]=i;
}else if(y!=fa)low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
for(scc++,now=0;now!=x;){
now=st[tp--];
is[now]=0;
bl[now]=scc;
}
return cd;
}
int main(){
for(scanf("%d%d",&n,&m),tot=1,i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y);
for(i=1;i<=n;i++)if(!dfn[i]){rt=i;if(dfs(i,0)>1)cut[++sz]=i;}
for(printf("%d\n",sz),i=1;i<=sz;i++)printf("%d\n",cut[i]);//割点
for(printf("%d\n",top),i=1;i<=top;i++)printf("%d %d\n",la[ans[i]],la[ans[i]^1]);//割边
for(puts(""),i=1;i<=n;i++)printf("%d\n",bl[i]);//属于的双联通分量
}
BZOJ1116 算出每个割点的贡献即可
#include<cstdio>
#include<algorithm>
#define N 101000
#define M 1001000
using namespace std;typedef long long LL;
int n,m,x,y,i,tot,tm,sz[N],fir[N],dfn[N],low[N],la[M],ne[M];LL ans[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
dfn[x]=low[x]=++tm;sz[x]=1;int i,y,now=0;
for(i=fir[x];i;i=ne[i]){
if(dfn[y=la[i]])low[x]=min(low[x],dfn[y]);else{
dfs(y);sz[x]+=sz[y];
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y])ans[x]+=(LL)now*sz[y],now+=sz[y];
}
}
ans[x]+=(LL)now*(n-now-1);
}
int main(){
for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(dfs(1),i=1;i<=n;i++)printf("%lld\n",(ans[i]+n-1)*2);
}
点双联通分量的缩点 对于点双连通分量，实际上在求割点的过程中就能顺便把每个点双连通分量求出。建立一个栈，存储当前双连通分量，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足dfn(u)<=low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分量。割点可以属于多个点双连通分量，其余点和每条边只属于且属于一个点双连通分量。
WF2011 H 求出所有割点，然后把剩下的点形成的每个联通块都变为一个点，缩点以后构新图变成一棵树，只要把树的所有叶子所在联通块的大小乘起来就可以了。注意当图中不存在割点时，最少要标记两个点，方案数n*(n-1)/2。
#include<bits/stdc++.h>
#define N 100100
#define CL(a) memset(a,0,sizeof a)
using namespace std;bool V[N];long long an;
int n,m,i,t,x,y,id,tot,scc,ca,w,e,cd,fir[N],la[N],ne[N],L[N],D[N],q[N],bl[N],sz[N],du[N],E[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int dfs(int x,int fa){
int i,y,cd=0,o=0;D[x]=L[x]=++id;
for(i=fir[x];i;i=ne[i])if(!D[y=la[i]]){
dfs(y,x);cd++;L[x]=min(L[x],L[y]);
if(x!=1&&D[x]<=L[y])V[x]=1;
}else if(y!=fa)L[x]=min(L[x],D[y]);
return cd;
}
void INS(int x,int y){if(x!=n+1)du[x]++,du[y]++;else E[++e]=y;}
void dfs(int x){
D[x]=L[x]=++id;q[++t]=x;int i,y,o;
for(i=fir[x];i;i=ne[i])if(!D[y=la[i]]){
dfs(y);L[x]=min(L[x],L[y]);if(x==1)cd++;
if(D[x]==L[y]){
V[x]=1;scc++;
do{
o=q[t--];bl[o]=scc;sz[scc]++;
if(V[o])INS(o+n,scc);
}while(y!=o);
INS(x+n,scc);sz[x+n]=sz[scc];
}
}else L[x]=min(L[x],D[y]);
}
int main(){
for(;scanf("%d",&m),m;n=tot=id=t=cd=e=scc=0,CL(fir),CL(D),CL(L),CL(V),CL(du),CL(sz)){
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x),n=max(n,max(x,y));
dfs(1);an=1;w=0;if(cd>1)for(i=1;i<=e;i++)du[n+1]++,du[E[i]]++;
for(i=1;i<=n;i++)if(du[i]==1)w++,an*=sz[i];
printf("Case %d: ",++ca);
if(scc>1)printf("%d %lld\n",w,an);else printf("2 %lld\n",1ll*n*(n-1)/2);
}
}
UOJ30 tourists 点双联通分量缩点后进行树剖，对于每个缩的边双联通分量用set记录最小值来维护答案即可。注意对于询问，最后如果x点在一个缩后的边双上，其父亲要特判一下，因为其父亲其实也是可以走的。
#include<bits/stdc++.h>
#define N 200100
using namespace std;vector<int>V[N];multiset<int>S[N];char s[3];
int n,m,Q,i,t,x,y,an,id,tot,scc,a[N],fir[N],q[N],lb[N],ne[N],la[N],E[N*3],st[N],to[N],bl[N],h[N],hs[N],F[N],dfn[N],low[N],sz[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void tj(int x,int fa){
dfn[x]=low[x]=++id;q[++t]=x;int i,y,o;
for(i=0;i<V[x].size();i++)if(!dfn[y=V[x][i]]){
tj(y,x);low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])for(ins(x,++scc),o=0;y!=o;S[scc].insert(a[o]))lb[o=q[t--]]=scc,ins(scc,o);
}else if(y!=fa)low[x]=min(low[x],dfn[y]);
}
void dfs(int x){
sz[x]=1;int i,y;for(i=fir[x];i;i=ne[i])if(F[x]!=la[i]){
F[y=la[i]]=x;h[y]=h[x]+1;dfs(y);sz[x]+=sz[y];
if(sz[y]>sz[hs[x]])hs[x]=y;
}
}
void dfs2(int x,int f){
st[x]=++id;to[id]=x;bl[x]=f;if(hs[x])dfs2(hs[x],f);
for(int i=fir[x];i;i=ne[i])if(F[x]!=la[i]&&la[i]!=hs[x])dfs2(la[i],la[i]);
}
void cg(int k,int l,int r,int x,int z){
if(l==r){E[k]=z;return;}int md=l+r>>1;
x<=md?cg(k<<1,l,md,x,z):cg(k<<1|1,md+1,r,x,z);E[k]=min(E[k<<1],E[k<<1|1]);
}
int qu(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return E[k];int md=l+r>>1,o=1e9;if(x<=md)o=qu(k<<1,l,md,x,y);
if(y>md)o=min(o,qu(k<<1|1,md+1,r,x,y));return o;
}
int main(){
for(scanf("%d%d%d",&n,&m,&Q),scc=n,i=1;i<=n;i++)scanf("%d",&a[i]);
for(;m--;V[x].push_back(y),V[y].push_back(x))scanf("%d%d",&x,&y);
for(tj(1,0),id=0,dfs(1),dfs2(1,1),i=1;i<=n;i++)cg(1,1,id,st[i],a[i]);
for(i=n+1;i<=id;i++)cg(1,1,id,st[i],*S[i].begin());
for(;Q--;){
scanf("%s%d%d",s,&x,&y);
if(s[0]=='C'){
if(lb[x]){
S[lb[x]].erase(S[lb[x]].find(a[x]));
S[lb[x]].insert(y);
cg(1,1,scc,st[lb[x]],*S[lb[x]].begin());
}
cg(1,1,scc,st[x],a[x]=y);
}else{
for(an=1e9;bl[x]!=bl[y];an=min(an,qu(1,1,scc,st[bl[x]],st[x])),x=F[bl[x]])if(h[bl[x]]<h[bl[y]])swap(x,y);
if(st[x]>st[y])swap(x,y);an=min(an,qu(1,1,scc,st[x],st[y]));
if(x>n&&F[x])an=min(an,a[F[x]]);printf("%d\n",an);
}
}
}
四、Dorminator Tree
Dorminator Tree大概就是判断一类有向图必经点的问题
先DFS构造出搜索树，然后按照dfn顺序处理，先处理出半必经点，然后根据半必经点处理出必经点
用idom[x]表示离点x最近的必经点，用semi[x]表示离点x最近的半必经点
半必经点的意思是，如果对于Y，存在某个点X通过一系列dfn[i]>dfn[Y]的点到达Y，那么X是Y的半必经点
对于每个点，我们只需要求dfn最小的半必经点。
对于一个节点Y，如果X能达到它，如果dfn[x]<dfn[y]，那么X是Y的半必经点，否则如果X在搜索树中的祖先Z使得dfn[Z]>dfn[Y]，那么semi[Z]也是Y的半必经点
然后每个点的semi[x]向x连边，这样构造出一个DAG，根据这个DAG可以求出idom
考虑搜索树上X和semi[X]的其它节点，选取这些点中dfn最小的记为Z
如果semi[Z]=semi[X]，那么idom[X]=semi[X]；否则idom[X]=idom[Z]
具体实现时按照dfn从大到小处理，用并查集维护比当前dfn大的点，然后用带权并查集维护出semi
总时间复杂度O((n+m)a(n))
#include<bits/stdc++.h>
#define N 100100
#define M 1101000
typedef long long LL;LL ans;
int n,m,i,j,x,y,tp,tot,fir[N],Fir[N],fiR[N],la[M],ne[M],dad[N],be[N],idom[N],semi[N],dfn[N],id[N],fa[N],sz[N];
int gf(int x){
if(dad[x]==x)return x;int y=gf(dad[x]);
if(dfn[semi[be[dad[x]]]]<dfn[semi[be[x]]])be[x]=be[dad[x]];
return dad[x]=y;
}
void ins(int x,int y,int *h){la[++tot]=y;ne[tot]=h[x];h[x]=tot;}
void dfs(int x){for(int i=fir[id[dfn[x]=++tp]=x];i;i=ne[i])if(!dfn[la[i]])fa[la[i]]=x,dfs(la[i]);}
int main(){
for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&x,&y),ins(x,y,fir),ins(y,x,fiR);
for(i=1;i<=n;i++)dad[i]=semi[i]=be[i]=i;
for(dfs(1),i=tp;i>1;i--){
for(j=fiR[x=id[i]];j;j=ne[j]){
if(!dfn[y=la[j]])continue;gf(y);
if(dfn[semi[be[y]]]<dfn[semi[x]])semi[x]=semi[be[y]];
}
for(ins(semi[x],x,Fir),dad[x]=fa[x],j=Fir[x=id[i-1]];j;j=ne[j])gf(y=la[j]),idom[y]=(semi[be[y]]==x)?x:be[y];
}
for(i=2;i<=tp;i++)if(idom[x=id[i]]!=semi[x])idom[x]=idom[idom[x]];
for(ans=(LL)tp*(tp-1)/2,i=tp;i>1;i--)if(++sz[x=id[i]],idom[x]!=1)sz[idom[x]]+=sz[x];else ans-=(LL)sz[x]*(sz[x]-1)/2;
printf("%lld",ans);
}
评论 (0)
