并查集学习总结

新手入门必备
并查集的定义：具有相同性质的集合可以拼成一个新的集合
所谓的拼接就是join（connect）函数

void join(int x,int y){
	int x=find_pre(x);
	int y=find_pre(y);
	if(x==y) return ;
	pre[x]=y;
}

find_pre函数是用来找一个集合的代表元
未优化前的find_pre(大概是O（n）)

int find_pre(int x){
	while(x!=pre[x]) x=pre[x];
	return x;
}

优化后的find_pre(大概是O（log(n)））

int find_pre(int x){
	return (x==pre[x]?x:pre[x]=find_pre(pre[x]))
}

集合

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int pre[maxn];
int find_pre(int x){
    return (x==pre[x])?x:pre[x]=find_pre(pre[x]);
}
优化后的find_pre()函数,复杂度是O（log(n)）
void connect(int x,int y){
    x=find_pre(x);
    y=find_pre(y);
    if(x==y) return ;
    pre[x]=y;
    return ;
}
拼接，复杂度是O（log(n)）
int n,prime[maxn],flag[maxn],num=0;
void find_prime(){
    for(int i=2;i<=n;i++){
        flag[i]=1;
    }
    for(int i=2;i<=n;i++){
        if(flag[i])
            prime[++num]=i;
        for(int j=1;j<=num&&1ll*i*prime[j]<=(ll)n;j++){
            flag[prime[j]*i]=0;
            if(i%prime[j]==0)
                break;
    }
    }
}
线筛求2----b范围的素数
int main(){
    int a,b,p,ans=0;
    scanf("%d%d%d",&a,&b,&p);
    for(int i=1;i<=b;i++)
        pre[i]=i;  构造集合
    n=b;
    find_prime();
    for(int i=p;i<=b;i++){
        if(flag[i]){
            int num=2;
            while(1ll*i*num<=(ll)b){
                connect(i,i*num);
                num++;
            }
        }
    }
    for(int i=a;i<=b;i++){
        if(find_pre(i)==i) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

家谱

思路
Map<string,strng>pre是字符串到字符串的映射。
#与+代表父亲与子女
我们可以以每一个父亲为一个代表元建立一个集合，如果一个集合的代表元是另外一个集合的元素的子女，那么把这个代表元的集合的代表元修改掉。

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
map<string,string>pre;
char a[maxn][10];
string find_pre(string x){
	return x==pre[x]?x:pre[x]=find_pre(pre[x]);
}
int main(){
	int num=1,pa=0;
	while(1){
		//printf("num=%d\n",num);
		scanf("%s",a+num);
		if(a[num][0]=='$') {num--;break;}
		if(a[num][0]!='?') pa++;
		num++;
	}
	for(int i=1;i<=pa;i++){
		if(a[i][0]=='#'){
			if(pre[a[i]+1].empty())
				pre[a[i]+1]=a[i]+1;
		}
		else {
			pre[a[i]+1]=pre[a[i-1]+1];
		}
	}
	for(int i=pa+1;i<=num;i++)
		cout<<a[i]+1<<' '<<find_pre(a[i]+1)<<endl;
    return 0;
}

部落划分

问题描述（转述）
n个野人划分成k个部落，问最优划分时最近的两个部落距离。
思路
由于n很小，对于O( $n^2$n2)也可以在1s内跑完，所以我们就可以用两个for循环跑出n个野人之间的距离

cnt=0;
for(int i=1;i<n;i++){
	for(int j=i+1;j<=n;j++){
		dis[++cnt](i,j)///表示第i个野人与第j个人的距离
	}
}

我们要考虑怎样把n个野人合并成k个部落？也就是如何最优地合并？
我们可以参考 $dis(i,j)$dis(i,j)，先把距离小的两个野人合并，依次类推合并 $（n-k）$（n−k）次变成 $k$k个部落。
那是不是我们只要把dis排序然后找第 $（n-k+1)$（n−k+1)的dis吗？
显然这里有一个bug $!!!!!!$!!!!!!
合并的时候需要考虑一点，如果这两个野人在同一个部落，那么合并他们也没有意义。因此，在合并的过程中我们需要check一下这两个野人是不是在同一个部落。

如何实现呢？
合并就直接套并查集

这里的x与y均表示第几个野人
int find_pre(int x){
    while(x!=pre[x]) x=pre[x];
    return x;
}
void join(int x,int y){
    x=find_pre(x);//x是原来的点
    y=find_pre(y);
    if(x==y) return ;
    pre[y]=x;
    return ;
}

如何check呢？（num表示合并次数，初始化为0）
在排好序的的dis里面逐一合并。dis[cnt] (i,j)表示i与j的距离，当枚举到i与j这个点的时候，若发现find_pre(i)与find_pre(j)相等 num不加，否则num++。直到num=n-k的时候，结束合并。

查找答案
假设最后一个合并的是dis[cnt]（i,j），是不是答案就是dis[cnt+1]呢？显然不是，如果dis[cnt+1] (i,j)中i与j是同一个部落的话，那么就要找cnt+2，以此类推找到ans。

上面思路所用的代码只是思考代码，下面的代码是AC代码。我建议自己看完思路尝试自己打代码这样才能真正理解。

#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
struct p{
    int x;
    int y;
};
struct bas{
    int val;
    int l;
    int r;
};
p pa[1000005];
bas que[1000005];
int pre[1000005];
int myabs(int x){
    return x>0?x:-x;
}
int find_pre(int x){
    while(x!=pre[x]) x=pre[x];
    return x;
}
void join(int x,int y){
    x=find_pre(x);//x是原来的点
    y=find_pre(y);
    if(x==y) return ;
    pre[y]=x;
    return ;
}
int Dis(int fir,int sec){
    int X=myabs(pa[fir].x-pa[sec].x);
    int Y=myabs(pa[fir].y-pa[sec].y);
    return X*X+Y*Y;
}
bool cmp(bas x,bas y){
    return x.val<y.val;
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        pre[i]=i;
        scanf("%d%d",&pa[i].x,&pa[i].y);
    }
    int beg=0;
    int res=n-k;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            que[++beg].val=Dis(i,j);
            que[beg].l=i;
            que[beg].r=j;
        }
    }
    sort(que+1,que+beg+1,cmp);
    int num=0;
    int i;
    for(i=1;i<=beg;i++){
        if(num==res) break;
        if(find_pre(que[i].l)==find_pre(que[i].r)) continue;
        num++;
        join(que[i].l,que[i].r);
    }
    int pp=i;
    while(find_pre(que[pp].l)==find_pre(que[pp].r)) pp++;
    double ans=sqrt(que[pp].val);
    printf("%.2f\n",ans);
    return 0;
}