猴子问题【并查集+边链表】

tonyfang posted @ 2016年6月06日 20:16 in NOIP with tags c++ oi , 1093 阅读

猴子问题

(monkey.pas/c/cpp)

【问题描述】

树上有n只猴子,它们编号为1~n。1号猴子用它的尾巴勾住一根树枝,其他的猴子有的被别的猴子抓住,有的抓住别的猴子,有的同时抓与被抓……每只猴子可以用它们的两只手,每只手至多抓住一只猴子。从0时刻开始,每秒会有一只猴子松开它的一只手。这也许会导致一些猴子掉到地上(猴子掉到地上也可以松手,掉落的时间忽略不计)。

    任务:

    编写一个程序完成:

    从输入中读取初始状态猴子如何挂在一起,以及猴子们松手的顺序;输出每只猴子掉到地上的时间。

 

【输入】

    输入的第一行包含两个正整数n和m,1 <= n <= 200000, 1 <= m <= 400000。n表示猴子的数量,m表示从0~m-1时刻每时刻有一只猴子松开它的一只手。接下来的n行描述猴子的初始状态。在第k+1行有两个正整数表示k号猴子两只手的情况:前一个数表示左手抓的猴子编号,后一个数表示右手抓的猴子编号,若为-1则该手是空的。接下来m行表示猴子松手的情况。每行有两个正整数a,b,表示a号猴子在该时刻放开它的一只手(b=1为左手,b=2为右手)。

【输出】

你的程序需要输出n个整数,每行一个。第i行的整数表示第i只猴子在何时刻掉到地上。若这只猴子不会掉到地上,则用-1表示。

【输入输出样例】

monkey.in

monkey.out

3 2

-1 3

3 -1

1 2

1 2

3 1

-1

1

1

【样例说明】

   初始状态为1号抓3号,2号抓3号,3号抓1号,3号抓2号。

   0时刻1号松左手,此时2号抓3号,3号抓1号,3号抓2号。

   1时刻3号松左手,此时3号抓2号,2号抓3号。由于2、3号都不与1号相连,所以两只猴子在1时刻掉到地上。

【数据范围】

    数据编号       N        M

   1         10000     9999

   2          100      106

   3          500      923

   4         1000      1600

   5         10000     19631

   6         20000     40000

   7         50000     100000

   8         100000    200000

   9         150000    270000

   10        200000    400000

【题解】

嗯很容易发现是要倒着做

那就是一个并查集的事情啦~

什么时候掉下来就是什么时候接到根(1)上

但是更新的时候是要更新一整个连通块

所以呢就要用边链表

合并的时候顺便合并边链表咯

一遍写完过样例好爽QAQ

# include <stdio.h>
# include <queue>
# include <stdlib.h>
# include <string.h>
using namespace std;
int fa[500010];
int n, m;
int left[500010], right[500010];
bool ll[500010], rr[500010];
int qa[500010], qb[500010];
int head[1000010], next[1000010], to[1000010], tot=0, vis[500010], ans[500010];
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}
inline void link(int u, int v) {
	add(u,v);
	add(v,u);
}
queue<int> q;
inline void bfs(int start, int vv) {
	while(!q.empty()) q.pop();
	q.push(start);
	vis[start] = vv;
	while(!q.empty()) {
		int top = q.front();
		q.pop();
		ans[top] = vv-1;
		for (int i=head[top]; i; i=next[i]) {
			if(vv != vis[to[i]]) {
				vis[to[i]] = vv;
				q.push(to[i]);
			}
		}
	}
}
int main() {
	freopen("monkey.in", "r", stdin);
	freopen("monkey.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i)
		scanf("%d%d", &left[i], &right[i]);
	for (int i=1; i<=m; ++i) {
		scanf("%d%d", &qa[i], &qb[i]);
		if(qb[i] == 1) ll[qa[i]] = 1;
		else rr[qa[i]] = 1;
	}
	for (int i=1; i<=n; ++i) fa[i] = i;
	int fu, fv, a, b, fw;
	for (int i=1; i<=n; ++i) {
		if(!ll[i] && left[i] != -1) {
			fu = getf(i), fv = getf(left[i]);
			if(fu != fv) {
				fa[fu] = fv;
				link(fu, fv);
			}
		}
		if(!rr[i] && right[i] != -1) {
			fu = getf(i), fv = getf(right[i]);
			if(fu != fv) {
				fa[fu] = fv;
				link(fu, fv);
			}
		}
	}
	for (int i=1; i<=n; ++i)
		ans[i] = -1;
	for (int i=m; i>=1; --i) {
		a = qa[i];
		if(qb[i] == 1) {
			if(left[qa[i]] != -1) b = left[qa[i]];
			else continue;
		} else {
			if(right[qa[i]] != -1) b = right[qa[i]];
			else continue;
		}
		fu = getf(a), fv = getf(b);
		fw = getf(1);
		if(fu == fw && fv != fw) {
			bfs(fv, i);
			fa[fv] = fw;
			link(fv, fw);
		} else if(fu != fw && fv == fw) {
			bfs(fu, i);
			fa[fu] = fw;
			link(fu, fw);
		} else if(fu != fv) {
			fa[fu] = fv;
			link(fu, fv);
		}
	}
	//ans[1] = -1;
	for (int i=1; i<=n; ++i) printf("%d\n", ans[i]);
	return 0;
}
10thmodelquestionpap 说:
2023年4月20日 00:58

10th Board Model Question Paper 2023 Aspirants who had Registered for the Board 10th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. 10thmodelquestionpaper.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.

como aceptar un alb 说:
2023年8月07日 14:11

Los álbumes compartidos le permiten cargar imágenes y videos en un álbum; otras personas pueden verlos y modificarlos, pero primero debe saber cómo unirse al álbum compartido antes de poder participar. Después de crear un álbum compartido y enviar invitaciones, cada persona que acepte la invitación puede agregar sus propias fotos y videos al álbum.Álbumes compartidos es una de las funciones como aceptar un album compartido preinstaladas de la aplicación Fotos de iOS. Esto le permite compartir fotos y videos con una persona en particular y hacer que lo mencionen. Alguien con quien haya intercambiado fotos o videos puede cargar sus propias imágenes y videos.

pavzi.com 说:
2024年1月12日 22:18

Pavzi website is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. pavzi.com We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter