NKOJ 2107 可爱的猴子（并查集）

发表于 |
字数统计: 1,008字 | 阅读时长 ≈ 4min

2107 可爱的猴子

问题描述

树上有n只猴子。它们编号为 1 到n。1 号猴子用它的尾巴勾着树枝。剩下的猴子都被其他的猴子用手抓着。每只猴子的每只手可以抓住另一只猴子的尾巴。从0 时刻开始，每一秒都有一只猴子松开它的一只手。这会导致一些猴子掉到地上（它们在地上也能继续松开它们的手，猴子落地的时间很短可以不计）。 你的任务是： 写一个程序，从标准输入读入猴子间抓与被抓住的关系信息，和它们放开手的顺 序，对于每一只猴子算出它落地的时间，把结果输出到标准输出。

输入格式

第一行有两个正整数n和m。n是猴子的数量，m是我们观察猴子的时间（单位为秒）。
接下来n行是初始情 况的描述。第k+1 行有两个整数表示第k个猴子抓住的猴子的编号，前一个数 代表左手抓的猴子的编号，后一个数是右手抓的猴子的编号。如果读入的数为-1 则代表猴子的手是空的。
接下来m行是对猴子观察的结果。在这m行里的第i行，有两个整数。前一个是猴子的编号，后一个是它在时刻i−1 时松开的手的编 号（1-左手，2-右手）。

输出格式

输出n个整数，每行一个。第i行表示第i个猴子落地的时间，如果在观察结束前猴子没有落地，那么输出-1

样例输入

3 2
-1 3
3 -1
1 2
1 2
3 1

样例输出

-1
1
1

提示

1≤n≤200000,1≤m≤400000

本题将猴子间的拉手关系看成边，依次删边倒着讨论变成依次加边，于是变成维护联通块的操作。

所以用并查集来维护联通块，加边过程中如果使原来不和1号点联通的点，与1号点联通了，就需要更新答案。问题在于存在已经掉下的猴子之间可能联通的情况，所以每次更新答案需要更新一个联通块，这是不容易实现的。

考虑到每个联通块只会更新一次答案，所以可以给每个点增加一个权值用来记录答案，合并的时候由于总是合并父亲，所以可以每次更新父亲的权值，用父亲的答案更新儿子的答案，从而在getfather的时候完成对联通块的更新，把所有点的初始权值设为无穷大即可。

最后需要注意将1号节点始终作为父亲。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define N 222222
#define M 1234567
using namespace std;
int n,m,F[N],A[N][3],D[N][3],ans[N],B[2*N],C[2*N];
int GF(int x)
{
	int t=F[x];
	if(F[x]!=x)F[x]=GF(F[x]);
	ans[x]=min(ans[x],ans[t]);
	return F[x];
}
void Merge(int x,int y,int z)
{
	int fx=GF(x),fy=GF(y);
	if(fx!=fy)
	{
		if(fx==1)swap(fx,fy);
		F[fx]=fy;
		ans[fx]=z;
	}
}
int main()
{
	int i,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&A[i][1],&A[i][2]);
		D[i][1]=A[i][1];
		D[i][2]=A[i][2];
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&B[i],&C[i]);
		A[B[i]][C[i]]=-1;
	}
	for(i=1;i<=n;i++)F[i]=i,ans[i]=1e9;
	for(i=1;i<=n;i++)
	{
		if(A[i][1]!=-1)Merge(i,A[i][1],1e9);
		if(A[i][2]!=-1)Merge(i,A[i][2],1e9);
	}
	for(i=m;i>=1;i--)
	{
		x=B[i];y=D[x][C[i]];
		if(y==-1)continue;
		Merge(x,y,i-1);
	}
	for(i=1;i<=n;i++)
	{
		GF(i);
		if(ans[i]!=1e9)printf("%d\n",ans[i]);
		else printf("-1\n");
	}
}