PAT_A1107
PAT甲级1107.
目录
A1107
题目
样例
输入:
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
输出:
3
4 3 1
思路和坑点
使用并查集统计不同的社团。对于每一个爱好,假设把数据中的第一个认为是该社团的代表,每次读取数据时,将相同爱好的人合并到同一个并查集(这里并查集的根指向一个负数——其绝对值代表该并查集的元素个数),最后遍历并查集,统计并查集的个数和人数,最后输出结果。
AC代码
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<set>
using namespace std;
#define MAXN 1003
int n;
vector<int> hobby(MAXN); //爱好数组,记录一个喜欢i的人的编号,作为该集团的根
vector<int> v(MAXN); //并查集 ,初始化为-1
int findfather(int a); //查询所属并查集的根结点
void Union(int a,int b); //合并两个并查集(由于此题规模比较小,可以不考虑合并时的大小)
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
fill(hobby.begin(),hobby.end(),-1); //初始化hobby数组为-1,表示所有的爱好暂时都没有人
fill(v.begin(),v.end(),-1); //并查集初始化为-1,表示每一个元素单独构成一个并查集,其中只有自己一个元素
scanf("%d",&n);
for(int i=1;i<=n;i++){ //读入第i个人的爱好
int num;
scanf("%d:",&num); //第i个人的爱好数量
for(int j=0;j<num;j++){
int h;
scanf("%d",&h);
if(hobby[h]==-1){ //如果是第一个喜欢h活动的人,更新hobby数组,即等同于将这个人作为hobby[h]社团的社长
hobby[h]=i;
}
else
Union(i,findfather(hobby[h])); //否则把i号人合并进入h爱好的社群
}
}
vector<int> out; //out用于输出结果
for(int i=1;i<=n;i++){
if(v[i]<0){ //如果i是并查集的根则进行统计
out.push_back(v[i]);
}
}
sort(out.begin(),out.end()); //对结果进行排序,由于并查集的根指向负数(其绝对值表示并查集元素个数),从小到大,也就是人数从大到小排序
cout<<out.size()<<'\n'; //输出社团个数
for(int i=0;i<out.size();i++){
if(i) putchar(' ');
printf("%d",-out[i]); //输出每个社团的人数
}
return 0;
}
int findfather(int a)
{
while(v[a]>0){ //并查集查找根,其中根指向一个负值
a=v[a];
}
return a;
}
void Union(int a,int b) //合并两个并查集
{
int fa=findfather(a); //先要找到两个并查集的根
int fb=findfather(b);
if(fa!=fb){ //如果两个元素不再同一个并查集中,则合并两个并查集
v[fa]+=v[fb]; //可以考虑将小的并查集并入大的并查集中,以减小并查集规模,加快查询速度
v[fb]=fa;
}
}