给定一个没有重复值的整形数组arr&＃xff0c;初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构&＃xff0c;并提供以下两个操作。 boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合 void union(int a, int b): 把a所在的集合与b所在的集合合并在一起&＃xff0c;原本两个集合各自的元素以后都算作同一个集合 [要求] 如果调用isSameSet和union的总次数逼近或超过O(N)&＃xff0c;请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)
int pre[1000001];// 1- N 不使用0 // 在main函数里面 fill(pre,pre&＃43;1000001,-1); 全设置成-1int findP(int a) //查找a所在集合的头领 {int pos&＃61;a;//保存a的值是为了下面的缩短路径while(pre[a]!&＃61;-1) //这两行很容易考虑到&＃xff0c;每一次找上一级&＃xff0c;直到集合的头领&＃xff0c;sn[头领]&＃61;-1a&＃61;pre[a];//这是a保存的就是集合的头领编号了while(pre[pos]!&＃61;-1) //从原先a到 头领之间的所有小头目都需要把上一级直接修改为头领{int curP&＃61;pre[pos];//保存上一级编号pre[pos]&＃61;a;//修改当前编号的上一级为集合头领pos&＃61;curP;}return a; }void union2(int a,int b) {if(!isSameSet(a,b)){//a的父亲是b的父亲了int ap&＃61;findP(a);sn[ap]&＃61;findP(b);findP(a);//这里是因为a所在的集合头领变为b所在集合的头领了&＃xff0c;所以a到原先头领之间的小头目都需要把首领改为b集合的首领} }
总AC代码
#include #include using namespace std; #include #include int pre[1000001];// 1- N 不使用0 int findP(int a) {int pos&＃61;a;while(pre[a]!&＃61;-1)a&＃61;pre[a];while(pre[pos]!&＃61;-1){int curP&＃61;pre[pos];pre[pos]&＃61;a;pos&＃61;curP;}return a; } bool isSameSet(int a, int b) {int ap&＃61;findP(a);int bp&＃61;findP(b);if(ap!&＃61;bp){return false;}elsereturn true; }void union2(int a,int b) {if(!isSameSet(a,b)){//a的父亲是b的父亲了int ap&＃61;findP(a);pre[ap]&＃61;findP(b);findP(a);} }int main() {fill(pre,pre&＃43;1000001,-1);int M,N;cin>>N>>M;for(int i&＃61;0;i}
#include #include using namespace std; #include #include int pre[1000001];// 1- N 不使用0 int findP(int x) {if (x !&＃61; pre[x]) pre[x] &＃61; findP(pre[x]);return pre[x]; }void union2(int a,int b) {//a的父亲是b的父亲了int ap&＃61;findP(a);int bp&＃61;findP(b);pre[ap]&＃61;findP(b);findP(a);}int main() {int M,N;cin>>N>>M;for(int i&＃61;1; i<&＃61;N; i&＃43;&＃43;){pre[i]&＃61;i;}for(int i&＃61;0; i}
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.
京公网安备 11010802041100号