冷战

wjh15101051's space

卧薪尝胆，厚积薄发。

冷战

Date: Sat Jul 21 00:13:20 CST 2018

In Category: NoCategory

Description：

$M$ 个操作： $1$ 、连接 $A$ 和 $B$ 。 $2$ 、询问 $A$ 和 $B$ 最早在加入第几条边时被联通。

$1\le N \le 500000$

Solution：

显然边在时间的最小生成树上。

将加入时间看作边权，加入的边权就是递增的，所以连接两个连通块之前两个连通块里的边权都小于这个边的边权，这样的话其实只要把这两个连通块连起来，连哪两个点对答案是没影响的，所以按秩合并就行了。

这样树的高度不超过 $log_2n$ ，于是暴力找 $LCA$ 复杂度是有保证的。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

int f[MAXN],v[MAXN],siz[MAXN];

int find(int x){return (x == f[x] ? x : find(f[x]));}

int deep(int x){return (x == f[x] ? 0 : deep(f[x]) + 1);}

void add(int x,int y,int z)

{

	x = find(x);y = find(y);

	if(x == y)return;

	if(siz[x] < siz[y]){f[x] = y;v[x] = z;siz[y] += siz[x];}

	else{f[y] = x;v[y] = z;siz[x] += siz[y];}

	return;

}

int query(int x,int y)

{

	if(find(x) != find(y))return 0;

	int dx = deep(x),dy = deep(y),ans = 0;

	while(dx < dy){ans = max(ans,v[y]);--dy;y = f[y];}

	while(dx > dy){ans = max(ans,v[x]);--dx;x = f[x];}

	while(x != y){ans = max(ans,max(v[x],v[y]));x = f[x];y = f[y];}

	return ans;

}

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		f[i] = i;siz[i] = 1;v[i] = 0;

	}

	int lastans = 0;

	int x,a,b;

	int tot = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&x,&a,&b);

		a = a ^ lastans;b = b ^ lastans;

		if(x == 0)add(a,b,++tot);

		else printf("%d\n",lastans = query(a,b));

	}

	return 0;

}

In tag: 数据结构-并查集

wjh15101051