强连通分量&2-SAT&双联通分量&Dorminator Tree

orz hhw posted @ 2015年5月10日 16:46 in 算法学习 with tags 模板 Tarjan 2-SAT bzoj 算法学习 联通分量 Dorminator Tree , 1984 阅读

这两天把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);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter