[HDU6271]Master of Connected Component

题目大意：

给出两棵\(n(n\le10000)\)个结点的以\(1\)为根的树\(T_a,T_b\)，和一个拥有\(m(m\le10000)\)个结点的图\(G\)。\(T_a,T_b\)的每一个结点上都有一个信息，表示\(G\)中的一条边\((u_i,v_i)\)。对于\(i\in[1,n]\)，询问从\(T_a\)和\(T_b\)上分别取出链\(1\sim i\)，将链上的信息所表示的边加入\(G\)中后，\(G\)中共有多少连通块。

思路：

对于\(T_a\)分块，对于\(T_a\)中的每一块，在\(T_b\)上DFS，若当前结点是\(T_a\)当前块内结点，则暴力加入\(T_b\)中所需要的边进行统计。加边、删边操作用栈记录并查集合并情况，并查集只按秩合并，不路径压缩，实现可拆分并查集。时间复杂度\(O(n\sqrt n\log n)\)。

源代码：

#include<cmath>

#include<stack>

#include<cstdio>

#include<cctype>

#include<vector>

#include<numeric>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

constexpr int N=10001;

int n,m,lim,ans[N],par[2][N],dep[N],dfn[N];

std::pair<int,int> w[2][N];

std::vector<int> e[2][N];

inline void clear() {

	dfn[0]=0;

	for(register int t=0;t<2;t++) {

		for(register int i=1;i<=n;i++) {

			e[t][i].clear();

			e[t][i].shrink_to_fit();

		}

	}

	std::fill(&ans[1],&ans[n]+1,0);

}

int top;

std::pair<int*,int> stack[N*4];

inline void push(int &x) {

	stack[++top]={&x,x};

}

inline void back(const int &tmp) {

	for(;tmp<top;top--) {

		*stack[top].first=stack[top].second;

	}

}

class DisjointSet {

	private:

		int anc[N],size[N];

		int find(const int &x) {

			return x==anc[x]?x:find(anc[x]);

		}

	public:

		void reset() {

			std::iota(&anc[1],&anc[m+1],1);

			std::fill(&size[1],&size[m+1],1);

		}

		void merge(const int &x,const int &y) {

			int p=find(x),q=find(y);

			if(p==q) return;

			if(size[p]>size[q]) std::swap(p,q);

			push(anc[p]);

			push(size[q]);

			anc[p]=q;

			size[q]+=size[p];

		}

};

DisjointSet s;

void solve(const int &x,const int &t) {

	const int tmp=top;

	s.merge(w[1][x].first,w[1][x].second);

	if(ans[x]==-1&&dfn[x]>=dfn[t]) {

		const int tmp=top;

		for(register int y=x;y!=t;y=par[0][y]) {

			s.merge(w[0][y].first,w[0][y].second);

		}

		ans[x]=m-top/2;

		back(tmp);

	}

	for(auto &y:e[1][x]) {

		solve(y,t);

	}

	back(tmp);

}

void dfs(const int &x) {

	const int tmp=top;

	s.merge(w[0][x].first,w[0][x].second);

	dep[x]=1;

	dfn[x]=++dfn[0];

	for(auto &y:e[0][x]) {

		dfs(y);

		dep[x]=std::max(dep[x],dep[y]+1);

	}

	ans[x]=-1;

	if(dep[x]==lim||x==1) {

		solve(1,x);

		dep[x]=0;

	}

	back(tmp);

}

int main() {

	for(register int T=getint();T;T--) {

		n=getint(),m=getint(),lim=sqrt(n);

		for(register int t=0;t<2;t++) {

			for(register int i=1;i<=n;i++) {

				w[t][i]={getint(),getint()};

			}

			for(register int i=1;i<n;i++) {

				const int u=getint(),v=getint();

				par[t][v]=u;

				e[t][u].push_back(v);

			}

		}

		s.reset();

		dfs(1);

		for(register int i=1;i<=n;i++) {

			printf("%d\n",ans[i]);

		}

		clear();

	}

	return 0;

}

巴特西

[HDU6271]Master of Connected Component

[HDU6271]Master of Connected Component

题目大意：

思路：

源代码：

最新文章

热门文章