差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:圆方树 [2021/08/04 19:25]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:圆方树 [2021/08/07 20:41] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== 圆方树 ======
+====== 广义圆方树 ======
 ===== 算法简介 =====
@@ 行 21: / 行 21: @@
 <code cpp>
 vector<int> g[MAXN<<1];
-int node_cnt;
+int node_cnt,val[MAXN<<1];
-int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_cnt;
+int low[MAXN],dfs_id[MAXN],dfs_t,bcc_cnt;
 vector<int> bcc[MAXN];
-stack<pair<int,int> >Stack;
+stack<int>Stack;
-bool iscut[MAXN];
 void dfs(int u,int fa){
 	low[u]=dfs_id[u]=++dfs_t;
-	blk_sz++;
+	Stack.push(u);
-	int child=0;
 	for(int i=head[u];i;i=edge[i].next){
 		int v=edge[i].to;
 		if(v==fa)continue;
 		if(!dfs_id[v]){
-			Stack.push(make_pair(u,v));
 			dfs(v,u);
 			low[u]=min(low[u],low[v]);
 			if(low[v]>=dfs_id[u]){
-				iscut[u]=true;
-				pair<int,int> temp;
 				bcc[++bcc_cnt].clear();
 				while(true){
-					temp=Stack.top();Stack.pop();
+					int temp=Stack.top();Stack.pop();
-					if(bcc_id[temp.first]!=bcc_cnt){
+					bcc[bcc_cnt].push_back(temp);
-						bcc_id[temp.first]=bcc_cnt;
+					if(temp==v)
-						bcc[bcc_cnt].push_back(temp.first);
-					}
-					if(bcc_id[temp.second]!=bcc_cnt){
-						bcc_id[temp.second]=bcc_cnt;
-						bcc[bcc_cnt].push_back(temp.second);
-					}
-					if(temp.first==u&&temp.second==v)
 					break;
 				}
-				node_cnt++;//就加了几行
+				bcc[bcc_cnt].push_back(u);
 				for(int node_id:bcc[bcc_cnt]){
 					g[node_cnt].push_back(node_id);
@@ 行 60: / 行 48: @@
 				}
 			}
-			child++;
-		}
-		else if(dfs_id[v]<dfs_id[u]){
-			Stack.push(make_pair(u,v));
-			low[u]=min(low[u],dfs_id[v]);
 		}
+		else if(dfs_id[v]<dfs_id[u])
+		low[u]=min(low[u],dfs_id[v]);
 	}
-	if(u==fa&&child<2)
-	iscut[u]=false;
 }
-void find_bcc(int n){
+void build_tree(int n){
 	mem(dfs_id,0);
-	mem(iscut,0);
-	mem(bcc_id,0);
 	dfs_t=bcc_cnt=0;
 	node_cnt=n;
 	_rep(i,1,n){
-		if(!dfs_id[i])
+		if(!dfs_id[i]){
-		dfs(i,i);
+			dfs(i,i);
+			Stack.pop();//别忘了清空根节点
+		}
 	}
 }
@@ 行 118: / 行 101: @@
 vector<int> g[MAXN<<1];
 int node_cnt,blk_sz,val[MAXN<<1];
-int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_cnt;
+int low[MAXN],dfs_id[MAXN],dfs_t,bcc_cnt;
 vector<int> bcc[MAXN];
-stack<pair<int,int> >Stack;
+stack<int>Stack;
-bool iscut[MAXN];
 void dfs(int u,int fa){
 	low[u]=dfs_id[u]=++dfs_t;
 	blk_sz++;
-	int child=0;
+	Stack.push(u);
 	for(int i=head[u];i;i=edge[i].next){
 		int v=edge[i].to;
 		if(v==fa)continue;
 		if(!dfs_id[v]){
-			Stack.push(make_pair(u,v));
 			dfs(v,u);
 			low[u]=min(low[u],low[v]);
 			if(low[v]>=dfs_id[u]){
-				iscut[u]=true;
-				pair<int,int> temp;
 				bcc[++bcc_cnt].clear();
 				while(true){
-					temp=Stack.top();Stack.pop();
+					int temp=Stack.top();Stack.pop();
-					if(bcc_id[temp.first]!=bcc_cnt){
+					bcc[bcc_cnt].push_back(temp);
-						bcc_id[temp.first]=bcc_cnt;
+					if(temp==v)
-						bcc[bcc_cnt].push_back(temp.first);
-					}
-					if(bcc_id[temp.second]!=bcc_cnt){
-						bcc_id[temp.second]=bcc_cnt;
-						bcc[bcc_cnt].push_back(temp.second);
-					}
-					if(temp.first==u&&temp.second==v)
 					break;
 				}
+				bcc[bcc_cnt].push_back(u);
 				val[++node_cnt]=bcc[bcc_cnt].size();
 				for(int node_id:bcc[bcc_cnt]){
@@ 行 156: / 行 129: @@
 				}
 			}
-			child++;
-		}
-		else if(dfs_id[v]<dfs_id[u]){
-			Stack.push(make_pair(u,v));
-			low[u]=min(low[u],dfs_id[v]);
 		}
+		else if(dfs_id[v]<dfs_id[u])
+		low[u]=min(low[u],dfs_id[v]);
 	}
-	if(u==fa&&child<2)
-	iscut[u]=false;
 }
 int sz[MAXN<<1];
@@ 行 181: / 行 149: @@
 	blk_sz=0;
 	dfs(rt,rt);
+	Stack.pop();
 	dfs2(rt,rt);
 }
-void find_bcc(int n){
+void build_tree(int n){
 	mem(dfs_id,0);
-	mem(iscut,0);
-	mem(bcc_id,0);
 	dfs_t=bcc_cnt=0;
 	node_cnt=n;
@@ 行 203: / 行 170: @@
 		Insert(v,u);
 	}
-	find_bcc(n);
+	build_tree(n);
 	enter(ans);
 	return 0;
@@ 行 357: / 行 324: @@
 		ans=min(ans,val[f[u]]);
 		return ans;
+	}
+}
+Edge edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int node_cnt;
+int low[MAXN],dfs_id[MAXN],dfs_t,bcc_cnt;
+vector<int> bcc[MAXN];
+stack<int>Stack;
+void dfs(int u,int fa){
+	low[u]=dfs_id[u]=++dfs_t;
+	Stack.push(u);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		if(!dfs_id[v]){
+			dfs(v,u);
+			low[u]=min(low[u],low[v]);
+			if(low[v]>=dfs_id[u]){
+				bcc[++bcc_cnt].clear();
+				while(true){
+					int temp=Stack.top();Stack.pop();
+					bcc[bcc_cnt].push_back(temp);
+					if(temp==v)
+					break;
+				}
+				bcc[bcc_cnt].push_back(u);
+				node_cnt++;
+				for(int node_id:bcc[bcc_cnt]){
+					Tree::Insert(node_cnt,node_id);
+					Tree::Insert(node_id,node_cnt);
+				}
+			}
+		}
+		else if(dfs_id[v]<dfs_id[u])
+		low[u]=min(low[u],dfs_id[v]);
+	}
+}
+int main(){
+	int n=read_int(),m=read_int(),q=read_int();
+	_rep(i,1,n)
+	Tree::val[i]=read_int();
+	while(m--){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	node_cnt=n;
+	dfs(1,1);
+	Stack.pop();
+	Tree::build(n);
+	while(q--){
+		char opt=get_char();
+		int u=read_int(),v=read_int();
+		if(opt=='A')
+		enter(Tree::query(u,v));
+		else
+		Tree::update(u,v);
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 例题三 ====
+[[https://www.luogu.com.cn/problem/P4606|洛谷p4606]]
+=== 题意 ===
+给定一个连通图。接下来多次询问，每次询问一个点集 $S$，求有多少点 $c$ 满足 $c\not\in S$ 且删去 $c$ 导致 $S$ 中的点不全部属于同一个连通分量。
+=== 题解 ===
+建圆方树，易知如果删除点 $c$ 导致 $u,v$ 之间在原图上不可达等价于删除点 $c$ 导致 $u,v$ 之间在圆方树上不可达。
+于是可以求 $S$ 中的点在圆方树上构成的虚树，易知答案为虚树中圆点数减去 $S$ 的点数。
+当然没有必要真的建立虚树，可以将圆点的点权转化为圆点到父结点的边权，然后求虚树的边权和，最后如果所有点的 $\text{LCA}$ 是圆点，则答案加一。
+至于求虚树的边权和是经典操作，只需要将关键点按 $\text{dfs}$ 排序后依次求相邻两点距离和再除以 $2$ 即可。时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXM=2e5+5,MAXN2=MAXN<<1;
+struct Edge{
+	int to,next;
+};
+namespace Tree{
+	Edge edge[MAXN2<<1];
+	int n,head[MAXN2],edge_cnt;
+	void Insert(int u,int v){
+		edge[++edge_cnt]=Edge{v,head[u]};
+		head[u]=edge_cnt;
+	}
+	int d[MAXN2],sz[MAXN2],f[MAXN2],dfs_id[MAXN2],dfs_t;
+	int h_son[MAXN2],mson[MAXN2],p[MAXN2],dis[MAXN2];
+	void clear(int n){
+		n<<=1;
+		dfs_t=edge_cnt=0;
+		_rep(i,1,n)
+		head[i]=0;
+	}
+	void dfs_1(int u,int fa,int depth){
+		sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+		dis[u]=dis[fa]+(u<=n);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==fa)
+			continue;
+			dfs_1(v,u,depth+1);
+			sz[u]+=sz[v];
+			if(sz[v]>mson[u]){
+				h_son[u]=v;
+				mson[u]=sz[v];
+			}
+		}
+	}
+	void dfs_2(int u,int top){
+		dfs_id[u]=++dfs_t;p[u]=top;
+		if(mson[u])
+		dfs_2(h_son[u],top);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==f[u]||v==h_son[u])
+			continue;
+			dfs_2(v,v);
+		}
+	}
+	void build(int _n){
+		n=_n;
+		dfs_1(1,0,0);
+		dfs_2(1,1);
+	}
+	int lca(int u,int v){
+		while(p[u]!=p[v]){
+			if(d[p[u]]<d[p[v]])
+			swap(u,v);
+			u=f[p[u]];
+		}
+		return d[u]<d[v]?u:v;
+	}
+	int query(int u,int v){
+		return dis[u]+dis[v]-2*dis[lca(u,v)];
 	}
 }
@@ 行 407: / 行 521: @@
 	}
 }
-int main(){
+int node[MAXN];
-	int n=read_int(),m=read_int(),q=read_int();
+bool cmp(int a,int b){
+	return Tree::dfs_id[a]<Tree::dfs_id[b];
+}
+void solve(){
+	int n=read_int(),m=read_int();
 	_rep(i,1,n)
-	Tree::val[i]=read_int();
+	head[i]=dfs_id[i]=bcc_id[i]=0;
+	bcc_cnt=dfs_t=edge_cnt=0;
+	Tree::clear(n);
 	while(m--){
 		int u=read_int(),v=read_int();
@@ 行 419: / 行 539: @@
 	dfs(1,1);
 	Tree::build(n);
+	int q=read_int();
+	while(q--){
+		int s=read_int();
+		_for(i,0,s)
+		node[i]=read_int();
+		sort(node,node+s,cmp);
+		int ans=0;
+		_for(i,0,s)
+		ans+=Tree::query(node[i],node[(i+1)%s]);
+		ans/=2;
+		if(Tree::lca(node[0],node[s-1])<=n)
+		ans++;
+		enter(ans-s);
+	}
+}
+int main(){
+	int T=read_int();
+	while(T--){
+		solve();
+	}
+	return 0;
+}
+</code>
+</hidden>
+====== 狭义圆方树 ======
+===== 算法简介 =====
+一种应用于仙人掌图的特殊圆方树。其中，定义仙人掌一类连通图，图中每条边至多出现在一个环中。
+===== 算法实现 =====
+[[https://www.luogu.com.cn/problem/P5236|洛谷p5236]]
+与广义圆方树的唯一区别在于狭义圆方树不存在大小为 $2$ 的双连通分量。
+这样，该图的所有连通分量大小至少为 $3$，且一定构成环。每个方点一定与圆点连边，但圆点也可能与圆点连边。
+由于仙人掌的特殊性，可以用圆方树求图中任意两点最短路。其中，对于大小为 $2$ 的连通分量，不添加方点，两圆点直接连边。
+对大小超过 $2$ 的连通分量，新建一个方点，每个点向方点连边，边权为该点到确立该连通分量的割点的环上最短距离。
+同时每个圆点也记录该点到确立该连通分量的割点的 $\text{Tarjan}$ 树上距离，每个方点记录环的总长度。
+查询时，如果两点 $\text{LCA}$ 为圆点，则答案就是最短距离。否则两个点先跳到 $\text{LCA}$ 的儿子，然后根据儿子点权和方点点权计算距离。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e4+5,MAXM=2e4+5;
+const int MAXN2=MAXN<<1;
+struct Edge{
+	int to,w,next;
+};
+namespace Tree{
+	Edge edge[MAXN2<<1];
+	int n,head[MAXN2],edge_cnt,val[MAXN2];
+	void Insert(int u,int v,int w){
+		edge[++edge_cnt]=Edge{v,w,head[u]};
+		head[u]=edge_cnt;
+	}
+	int d[MAXN2],sz[MAXN2],f[MAXN2],dfs_id[MAXN2],dfs_t;
+	int h_son[MAXN2],mson[MAXN2],p[MAXN2];
+	LL dis[MAXN2];
+	void dfs_1(int u,int fa,int depth){
+		sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==fa)
+			continue;
+			dis[v]=dis[u]+edge[i].w;
+			dfs_1(v,u,depth+1);
+			sz[u]+=sz[v];
+			if(sz[v]>mson[u]){
+				h_son[u]=v;
+				mson[u]=sz[v];
+			}
+		}
+	}
+	void dfs_2(int u,int top){
+		dfs_id[u]=++dfs_t;p[u]=top;
+		if(mson[u])
+		dfs_2(h_son[u],top);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==f[u]||v==h_son[u])
+			continue;
+			dfs_2(v,v);
+		}
+	}
+	void build(int _n){
+		n=_n;
+		dfs_1(1,0,0);
+		dfs_2(1,1);
+	}
+	int find_son(int u,int anc){
+		int son;
+		while(p[u]!=p[anc]){
+			son=p[u];
+			u=f[p[u]];
+		}
+		return u==anc?son:h_son[anc];
+	}
+	int LCA(int u,int v){
+		while(p[u]!=p[v]){
+			if(d[p[u]]<d[p[v]])swap(u,v);
+			u=f[p[u]];
+		}
+		return d[u]<d[v]?u:v;
+	}
+	int query(int u,int v){
+		int p=LCA(u,v);
+		if(p<=n)
+		return dis[u]+dis[v]-dis[p]*2;
+		else{
+			int p1=find_son(u,p),p2=find_son(v,p);
+			int d=min(abs(val[p1]-val[p2]),val[p]-abs(val[p1]-val[p2]));
+			return dis[u]-dis[p1]+dis[v]-dis[p2]+d;
+		}
+	}
+}
+Edge edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+int node_cnt,val[MAXN<<1];
+int low[MAXN],dfs_id[MAXN],f[MAXN],dfs_t,bcc_cnt;
+LL dis[MAXN];
+void link(int u,int v,int w){
+	LL s=dis[v]-dis[u]+w;
+	Tree::val[++node_cnt]=s;
+	int pos=v;
+	while(pos!=f[u]){
+		int w2=min(dis[pos]-dis[u],s-(dis[pos]-dis[u]));
+		Tree::Insert(node_cnt,pos,w2);
+		Tree::Insert(pos,node_cnt,w2);
+		Tree::val[pos]=dis[pos]-dis[u];
+		pos=f[pos];
+	}
+}
+void dfs(int u){
+	low[u]=dfs_id[u]=++dfs_t;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==f[u])continue;
+		if(!dfs_id[v]){
+			dis[v]=dis[u]+edge[i].w;
+			f[v]=u;
+			dfs(v);
+			low[u]=min(low[u],low[v]);
+			if(low[v]>dfs_id[u])
+			Tree::Insert(u,v,edge[i].w);
+		}
+		else if(dfs_id[v]<dfs_id[u])
+		low[u]=min(low[u],dfs_id[v]);
+		else
+		link(u,v,edge[i].w);
+	}
+}
+void build_tree(int n){
+	mem(dfs_id,0);
+	mem(f,0);
+	dfs_t=bcc_cnt=0;
+	node_cnt=n;
+	dfs(1);
+	Tree::build(n);
+}
+int main(){
+	int n=read_int(),m=read_int(),q=read_int();
+	while(m--){
+		int u=read_int(),v=read_int(),w=read_int();
+		Insert(u,v,w);
+		Insert(v,u,w);
+	}
+	build_tree(n);
 	while(q--){
-		char opt=get_char();
 		int u=read_int(),v=read_int();
-		if(opt=='A')
 		enter(Tree::query(u,v));
-		else
-		Tree::update(u,v);
 	}
 	return 0;

CVBB ACM Team

用户工具

站点工具

差别

页面工具