牛客并查集 先练练手，因为有测试数据

链接：https://www.nowcoder.com/questionTerminal/e7ed657974934a30b2010046536a5372
来源：牛客网

给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。
boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
void union(int a, int b): 把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合
[要求]
如果调用isSameSet和union的总次数逼近或超过O(N)，请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)

输入描述:
第一行两个整数N, M。分别表示数组大小、操作次数
接下来M行，每行有一个整数opt
若opt = 1，后面有两个数x, y，表示查询(x, y)这两个数是否属于同一个集合
若opt = 2，后面有两个数x, y，表示把x, y所在的集合合并在一起

输出描述:
对于每个opt = 1的操作，若为真则输出"Yes"，否则输出"No"
示例1
输入
4 5
1 1 2
2 2 3
2 1 3
1 1 1
1 2 3
输出
No
Yes
Yes
说明
每次2操作后的集合为
({1}, {2}, {3}, {4})
({1}, {2, 3}, {4})
({1, 2, 3}, {4})

备注:

牛客并查集最初思路

并查集之前的实现也都是两个函数，一个查找结合头领的函数，一个合并集合的函数。

这里N是在1到10^6之间，所以直接声明个全局数组，全部赋值为-1。

int pre[1000001];// 1-  N 不使用0  
// 在main函数里面 fill(pre,pre+1000001,-1); 全设置成-1int findP(int a)  //查找a所在集合的头领
{int pos=a;//保存a的值是为了下面的缩短路径while(pre[a]!=-1)  //这两行很容易考虑到，每一次找上一级，直到集合的头领，sn[头领]=-1a=pre[a];//这是a保存的就是集合的头领编号了while(pre[pos]!=-1) //从原先a到 头领之间的所有小头目都需要把上一级直接修改为头领{int curP=pre[pos];//保存上一级编号pre[pos]=a;//修改当前编号的上一级为集合头领pos=curP;}return a;
}void union2(int a,int b)
{if(!isSameSet(a,b)){//a的父亲是b的父亲了int ap=findP(a);sn[ap]=findP(b);findP(a);//这里是因为a所在的集合头领变为b所在集合的头领了，所以a到原先头领之间的小头目都需要把首领改为b集合的首领}
}

总AC代码

#include <iostream>
#include <string>
using namespace std;
#include<algorithm>
#include<queue>
int pre[1000001];// 1-  N 不使用0
int findP(int a)
{int pos=a;while(pre[a]!=-1)a=pre[a];while(pre[pos]!=-1){int curP=pre[pos];pre[pos]=a;pos=curP;}return a;
}
bool isSameSet(int a, int b)
{int ap=findP(a);int bp=findP(b);if(ap!=bp){return false;}elsereturn true;
}void union2(int a,int b)
{if(!isSameSet(a,b)){//a的父亲是b的父亲了int ap=findP(a);pre[ap]=findP(b);findP(a);}
}int main()
{fill(pre,pre+1000001,-1);int M,N;cin>>N>>M;for(int i=0;i<M;i++){int op;int a,b;scanf("%d %d %d",&op,&a,&b);if(op==1){if(isSameSet(a,b)==1)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}else{union2(a,b);}}return 0;
}

牛客并查集时间改进（可以直接看这个）

之后在牛客的测试发现，上述的代码的时间有时候能AC有时候不能AC 小无奈，优化了一下。
并查集之前的实现也都是两个函数，一个查找结合头领的函数，一个合并集合的函数。

这里N是在1到10^6之间，所以直接声明个全局数组pre，pre[i] 保存编号i的头领，默认自己是自己的头领。
主要改进在findP函数，因为自己是自己的首领了，直接递归调用搞定，很简单，而且时间效率更高（这其实我有点不太理解，因为我感觉递归时间效率并不高）

#include <iostream>
#include <string>
using namespace std;
#include<algorithm>
#include<queue>
int pre[1000001];// 1-  N 不使用0
int findP(int x)
{if (x != pre[x]) pre[x] = findP(pre[x]);return pre[x];
}void union2(int a,int b)
{//a的父亲是b的父亲了int ap=findP(a);int bp=findP(b);pre[ap]=findP(b);findP(a);}int main()
{int M,N;cin>>N>>M;for(int i=1; i<=N; i++){pre[i]=i;}for(int i=0; i<M; i++){int op;int a,b;scanf("%d %d %d",&op,&a,&b);if(op==1){if(findP(a)==findP(b))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}else{union2(a,b);}}return 0;
}

PAT

1107 Social Clusters (30分)
When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A social cluster is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:

K
​i
​​ : h
​i
​​ [1] h
​i
​​ [2] … h
​i
​​ [K
​i
​​ ]

where K
​i
​​ (>0) is the number of hobbies, and h
​i
​​ [j] is the index of the j-th hobby, which is an integer in [1, 1000].

Output Specification:
For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
Sample Output:
3
4 3 1

做了牛客那道题，再看这题其实只要 考虑一件事，如何把兴趣一样的人关联起来，我是设置了一个 hobby[1001]={0} 然后只要hobby[兴趣编号]==0 就把hobby[兴趣编号]=人的编号 ，这样每一个性趣编号我们就有了一个头领了，然后之后的人的编号就直接用并查集的合并函数就OK了

然后输出的时候我不知道怎么想的 人家map的有序是指的key有序，不是value有序，以为那里思路不对，验证了好久。。。。无奈

AC代码

#include <iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;int pre[1001];// 1-  N 不使用0
int findP(int x)
{if (x != pre[x]) pre[x] = findP(pre[x]);return pre[x];
}void union2(int a,int b)
{//a的父亲是b的父亲了int ap=findP(a);int bp=findP(b);pre[ap]=bp;findP(a);//这一步其实用不用都行，因为后面会吧所有人的编号在进行一次find 压缩路径}int main()
{int N;cin>>N;//初始化并查集使用的首领数组for(int i=1; i<=N; i++){pre[i]=i;}int hobby[1001]= {0};for(int i=1; i<=N; i++){int Num;scanf("%d: ",&Num);while(Num>0){Num--;int get;cin>>get;if(hobby[get]==0)hobby[get]=i;else{union2(hobby[get],i);}}}for(int i=1; i<=N; i++){findP(i);}//输出map<int,int> mapp;for(int i=1; i<=N; i++){mapp[pre[i]]++;}cout<<mapp.size()<<endl;vector<int> vec;for(auto it=mapp.rbegin(); it!=mapp.rend(); it++){vec.push_back(it->second);}sort(vec.begin(),vec.end());for(int i=vec.size()-1;i>=0;i--){if(i==vec.size()-1){cout<<vec[i];}elsecout<<' '<<vec[i];}return 0;
}