Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

【学习】启发式合并

Jacinth posted @ 2016年5月05日 21:03 in Lerning with tags 学习 Learning 启发式合并 , 645 阅读

感觉很早以前就被黈力教导过启发式合并

根本不懂为什么这样就log了呢

其实就是把小的那部分并到大的那部分呢

1483: [HNOI2009]梦幻布丁

唔。。邻接表和启发式合并

然后就没有辣

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;

#define NN 1000005

int read()
{
	char ch; int f=1,xx=0;
	for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (xx=0;ch>='0';ch=getchar()) xx=xx*10+ch-'0'; xx*=f;
	return xx;
}

int n,m,fa[NN],c[NN],a[NN],head[NN],ne[NN],now[NN],tmp,x,y,type,ans=0;

int main()
{
	n = read(), m = read();
	for (int i=1;i<=n;++i)
	{
		a[i] = read();
		c[a[i]] ++;
		fa[a[i]] = a[i];
		if (a[i] != a[i-1]) ++ans;
		if (!head[a[i]]) head[a[i]] = i;
		ne[now[a[i]]] = i;
		now[a[i]] = i;
	}
	while (m--)
	{
		type = read();
		if (type == 2) printf("%d\n", ans);
		else
		{
			x = read() , y = read();
			if (x == y) continue;
			if (c[fa[x]] > c[fa[y]]) swap(fa[x], fa[y]);
			x = fa[x], y = fa[y];
			if (c[x] == 0) continue;
			for (int i=head[x]; i ; i=ne[i])
			{
				tmp=i;
				if (y == a[i+1]) ans--;
				if (y == a[i-1]) ans--;
			}
			for (int i=head[x]; i ; i=ne[i]) a[i] = y;
			ne[tmp] = head[y], head[y] = head[x], c[y] += c[x], head[x] = c[x] = 0;
		}
	}
	return 0;
}
Avatar_small
AP SSC Biology Quest 说:
2022年9月14日 16:27

Candidates can download 10th class biology subject sample papers pdf and key topics with assignments in all exam formats of the board like SA-1, SA-2, FA-1, FA-2, FA-3 and FA-4.Telugu Medium, AP SSC Biology Question PaperEnglish Medium and Urdu Medium Students of the State who studying Class 10th Grade can download the AP SSC Biology Model Papers 2023 for theory, objective and bit questions to Self Practice.Telugu Medium, English Medium and Urdu Medium Students of the State who studying Class 10th Grade can download the AP SSC Biology Model Papers 2023 for theory, objective and bit questions to Self Practice.


登录 *


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