C++——NOIP模拟题——猴子

有 N 只猴子，第一只尾巴挂在树上，剩下的 N-1 只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。当然一只猴子最多抓两只另外的猴子，只有两只手嘛。现在给出这N只猴子抓与被抓的信息。

在某个时刻某只猴子 A 会放掉它左手或右手的猴子 B ，会出现以下三种情况：
1．B 起初并没有抓住 A，则 B 会掉下；
2．B 起初也抓住了 A，但在 A 放手的同时 B 并没有放手，则 B 不会掉下；
3．B 起初也抓住了 A，在 A 放手的同时 B 也放手了，则 B 会掉下。

如果 B 掉下，就会同时导致相关猴子也落到地上。求每只猴子的落地的时间。

第一行两个数 N、M，表示有 N 只猴子，并且总时间为 M-1 。

接下来 N 行，按编号从 1..N 描述了每只猴子的信息，每行两个整数，第 i 行的两个数分别表示第 i 只猴子的左手和右手抓的猴子的编号，如果是 -1 ，表示该猴子那只手没抓其他的猴子。再接下来 M 行，按时间顺序（0~M-1）给出了一些猴子放手的信息，第 1+N+i 行表示第 i-1 时刻某只猴子的放手信息，信息以两个数给出，前者表示放手的猴子的编号，后者表示其放的是哪只手，1 左 2 右。

共输出 N 行，第 i 行表示第 i 只猴子掉落的时刻，若第 i 只猴子到 M-1 时刻以后还没掉落，就输出 -1 。

输入

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

输出

-1 
1 
1

【数据范围】
30% 的数据，N≤1000；M≤1000；
100% 的数据，1≤N≤200000；1≤M≤400000。

解题报告：

可以把每个猴子看成图中的一个点，猴子之间的关系用无向边来表示，判断一只猴子是否掉落就看其与 1 是否在同一个连通分量中。顺着思考问题可能有点困难，可以反过来思考，首先可以求出第 M-1 时刻之后猴子们的情况，然后倒着来，将猴子一只只“接”上去，这样问题就变成一只猴子最早在什么时候和 1 所处的连通块并在了一起。对于连通性的维护可以用并查集来实现。

时间效率：
我们用并查集来实现连通性的维护，总的时间效率为O(n*α)，其中α为不超过5的数，可以视为常数。

空间效率： 0(N+M)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
int n,m,cnt,hand[200001][2],ret[400001],t[400001][2],graph[400001],time[400001][2];
bool sign[400001];
struct node{
	int tvtx,last;
}arc[2000001];
inline int readint()
{
    int i=0,f=1;
    char ch;
    for(ch=getchar();(ch<'0'||ch>'9') && ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-1; 
        ch=getchar();
    }
    for(;ch>='0' && ch<='9';ch=getchar())
        i=(i<<3)+(i<<1)+ch-'0';
    return i*f;
}
inline void add(int a,int b)
{
	arc[++cnt].tvtx=b;
	arc[cnt].last=graph[a];
	graph[a]=cnt;
}
inline void dfs(int x,int t)
{
	sign[x]=1;
	ret[x]=t;
	for(int i=graph[x];i;i=arc[i].last)
	{
		int v=arc[i].tvtx;
		if(!sign[v]) dfs(v,t);
	}
}
int main()
{
	register int i,j,a,b;
	n=readint();
	m=readint();
	for(i=1;i<=n;++i) hand[i][0]=readint(),hand[i][1]=readint();
	memset(time,-1,sizeof(time));
	for(i=1;i<=n;++i) ret[i]=-2;
	for(i=0;i<m;++i)
	{
		t[i][0]=readint();
		t[i][1]=readint();
		time[t[i][0]][t[i][1]-1]=i;
		t[i][1]=hand[t[i][0]][t[i][1]-1];
	}
	for(i=1;i<=n;++i)
		for(j=0;j<=1;++j)
			if(hand[i][j]!=-1&&time[i][j]==-1)
			{
				add(i,hand[i][j]);
				add(hand[i][j],i);
			}
	dfs(1,-1);
	for(i=m-1;i>=0;--i)
	{
		a=t[i][0];
		b=t[i][1];
		add(a,b);
		add(b,a);
		if(sign[a]&&!sign[b]) dfs(b,i);
		if(sign[b]&&!sign[a]) dfs(a,i);
	}
	for(i=1;i<=n;++i) printf("%d\n",ret[i]);
}