关于算法-数据结构:PAT甲级1107-Social-Clusters

题目粗心：

有 N 集体, 如果任意 2 集体的喜好有雷同的 (就是有交加), 那么这 2 集体就是属于同一个社交网络, 要求输入这 N 集体组成了几个社交网络, 并且输入每个社交网络的人数

算法思路：

此题考查的是并查集的应用 (并查集次要用来解决 若干个节点，有些节点相互相连，有些节点没有连贯，如何判断其中两个节点是否相连这样的问题)，目前来看，应用并查集求解此题应该是最好的抉择，能够应用构建人与人的关系图，而后遍历有多少个连通重量，每一个连通重量有多少节点，然而这种形式实现起来过于简单。

并查集次要由 1 个汇合，2 个操作所组成，汇合就是 father 保留每一个节点的父节点，2 个操作别离是查问节点 x 的父亲节点和合并 2 个节点所在的汇合。入上面代码所示：

int father[1005];// 每一个节点的父亲节点
 
// 查问节点 x 的父亲节点
int findFather(int x){while(x!=father[x]){x = father[x];
    }
    return x;//father[x]== x 的才是根节点
}
 
// 合并 a 和 b 节点所在的汇合
void Union(int a,int b){int fa = findFather(a);
    int fb = findFather(b);
    if(fa!=fb){father[fa] = fb;
    }
}

在此题中，咱们须要构建一个人与人之间互相关联的社交网络，媒介是每一个人所领有的喜好，那么咱们应用 $hobbyOwner$ 记录每一个喜好的所有者，这样在输出每一个喜好的时候，如果以后喜好没有所有者，将以后喜好标记为本人所独有，否则就将该喜好所有者和以后人合并到一个社交网络。在每一个社交网络构建实现后，咱们须要统计社交网络的个数和每一个社交网络的人数，咱们应用 $roots(set 汇合)$ 保留每一个社交网络的根节点，其个数即为社交网络的个数，$cluster$ 保留每一个社交网络的人数，具体做法就是，须要遍历每一个人，找到其根节点 $root$，而后增加进 $roots$ 中，并且统计以后社交网络的人数 ++cluster[root]。最初对 cluster 进行排序输入即可。

int cluster[1005];// 每一个社交网络的人数
unordered_set<int> roots;// 保留每一个根节点
 
// 统计社交网络的个数, 也就是根节点的个数
for (int k = 1; k <= N; ++k) {int root = findFather(k);
    ++cluster[root];
    roots.insert(root);
}

留神点：

• 1、有一种状况须要特地留神，如果当初曾经组建好了社交网络 A 和 B，那么当初有一个人的喜好既有 A 又有 B，那么他将作为连贯 A 和 B 的桥梁，须要将每一个人的所有喜好都要进行解决，并且因为合并后，只更新了一个社交网络的根节点的父亲，该社交网络的其余节点的父亲仍然没有变动，所以在统计社交网络的人数的时候不能间接应用 father 数组，肯定得从新遍历每一个节点获取其父亲，否则测试点 1，4，5 会谬误。

提交后果：

AC 代码：

#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
 
using namespace std;
 
int father[1005];// 每一个节点的父亲节点
unordered_map<int,int> hobbyOwner;// 每一个喜好的所有者
int cluster[1005];// 每一个社交网络的人数
 
// 初始化每一个节点的父亲
void init(){for (int i = 1; i <= 1000; ++i) {father[i] = i;
    }
}
 
// 查问节点 x 的父亲节点
int findFather(int x){while(x!=father[x]){x = father[x];
    }
    return x;//father[x]== x 的才是根节点
}
 
// 合并 a 和 b 节点所在的汇合
void Union(int a,int b){int fa = findFather(a);
    int fb = findFather(b);
    if(fa!=fb){father[fa] = fb;
    }
}
 
bool cmp(int a,int b){return a>b;}
 
int main()
{init();
    int N;// 节点个数
    scanf("%d",&N);
    for (int i = 1; i <= N; ++i) {
        int K;
        scanf("%d:",&K);
        for (int j = 0; j < K; ++j) {
            int hobby;
            scanf("%d",&hobby);
            if(hobbyOwner[hobby]==0){
                // 以后喜好没有人领有
                hobbyOwner[hobby] = i;
            } else {
                // 曾经领有了，合并拥有者和 i
                Union(hobbyOwner[hobby],i);
            }
        }
    }
    unordered_set<int> roots;// 保留每一个根节点
    // 统计社交网络的个数, 也就是根节点的个数
    for (int k = 1; k <= N; ++k) {int root = findFather(k);
        ++cluster[root];
        roots.insert(root);
    }
    printf("%lu\n",roots.size());
    sort(cluster+1,cluster+N+1,cmp);
    for(int i=1;i<=roots.size();++i){printf("%d",cluster[i]);
        if(i<roots.size()) printf(" ");
    }
    return 0;
}