【pta】社交集群 (30分)（并查集）

当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。

输入格式： 输入在第一行给出一个正整数 N（≤1000），为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N 行，每行按以下格式给出一个人的兴趣爱好列表： Ki: h[1] h[2] … h[Ki]

其中K​​ (>0)是兴趣爱好的个数，h​i​​ [j]是第j个兴趣爱好的编号，为区间 [1, 1000] 内的整数。 输出格式： 首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。

输入样例：

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

两种解法： 1.先把兴趣添加到并查集组合，然后统计人数

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<map> using namespace std; const int inf=0x3f3f3f3f; const int N=1005; typedef long long ll; int a[N],b[N],v[N],s[N]; int find(int x){ return a[x]==x?x:(a[x]=find(a[x])); } int cmp(int x,int y){ return x>y; } void join(int x,int y){ x=find(x); y=find(y); if(x!=y){ a[y]=x; } } int main() { int x,y,i,j,n,m,ans=0; scanf("%d",&n); for(i=1;i<=1000;i++){ a[i]=i; } for(i=1;i<=n;i++){ scanf("%d:%d",&m,&x); s[i]=x; while(--m){ scanf("%d",&y); join(x,y); } } for(i=1;i<=n;i++){ b[find(s[i])]++; } for(i=1;i<=1000;i++){ if(b[i]){ ans++; } } sort(b+1,b+1000+1,cmp); printf("%d\n",ans); for(i=1;i<=ans;i++){ if(i!=1) printf(" "); printf("%d",b[i]); } return 0; }

2.先把每个人添加到第一个兴趣里，然后统计每个兴趣集合的人数

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<map> using namespace std; const int inf=0x3f3f3f3f; const int N=1005; typedef long long ll; int a[N],b[N],v[N]; int find(int x){ return a[x]==x?x:(a[x]=find(a[x])); } void join(int x,int y){ x=find(x); y=find(y); if(x!=y){ a[y]=x; } } int main() { int x,y,i,j,n,m,ans=0; scanf("%d",&n); for(i=1;i<=1000;i++){ a[i]=i; } for(i=1;i<=n;i++){ scanf("%d:%d",&m,&x); v[x]++; while(--m){ scanf("%d",&y); join(x,y); } } for(i=1;i<=1000;i++){ if(v[i]){ int x=find(i); if(b[x]==0) ans++; b[x]+=v[i]; } } sort(b+1,b+1000+1,greater<int>()); printf("%d\n",ans); for(i=1;i<=ans;i++){ if(i!=1) printf(" "); printf("%d",b[i]); } return 0; }

开始中间有一部分写成了这样的，然而并不对，改了二十分钟。。。后来找到原因是x的值每次与y合并后都在更新，并不是一成不变的。

scanf("%d:%d",&m,&x); s[i]=x; x=find(x); while(--m){ scanf("%d",&y); int y=find(y); if(x!=y){ a[y]=x; } }