距离PAT考试还有17天,最重要的是做透每一题
(1)
思路:
基本就是利用并查集
以人的标号为集合元素然后通过爱好来合并各个集合
这里有个技巧是用一个数组hobby来做映射,hobby数组全部初始为0,然后一旦有一个人有这个hobby就将这个人的标号存进去
下次一旦再有人是这个hobby就和hobby中存的那个人的集合合并从而达到相应的效果
#include <cstdio> #include <cstring> #include <vector> #include <set> #include <algorithm> using namespace std; #define M 1010 int p[M]; int hobby[M]; int num[M]; int cnt; bool cmp(int a,int b) {return a>b;} void makeset(int x) { p[x]=x; num[x]=1; } int findset(int x) { int px=x,i; while(px != p[px]) px=p[px]; // find root while(x != px) { //path compression i=p[x]; p[x]=px; x=i; } return px; } void unionset(int x,int y) { x=findset(x); y=findset(y); p[x]=y; cnt--; } int main() { int n; scanf("%d",&n); cnt=n; memset(hobby,0,sizeof(hobby)); memset(p,0,sizeof(p)); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) { int k; scanf("%d:",&k); makeset(i); for(int j=0;j<k;j++) { int h; scanf("%d",&h); if(hobby[h] != 0) unionset(hobby[h],i); hobby[h]=i; } } printf("%d\n",cnt); for(int i=1;i<=n;i++){ num[findset(i)]++; } sort(num,num+M,cmp); //这里这样做是因为根节点的值一定是最大的其他节点最多也就是1 //排序后,大的cnt个节点一定在前面 for(int i=0;i<cnt;i++) {//减一是因为父节点自己也会把自己再算一次 i==0? printf("%d",num[i]-1):printf(" %d",num[i]-1); } return 0; }
这里研究一下并查集
它维护一些不想交的集合,它是集合的集合
接口是
void makeset(int i);
int findset(int x);
void unionset(int x,int y);
具体如下:
void makeset(int x) { p[x]=x; rank[x]=0; }这里rank是为了记录深度以提高效率而做的
int findset(int x) { int px=x; while(px!=p[px]) px=p[px];//find root while(x!=px) { //root compression i=p[x]; p[x]=px; x=i; } return px; }
为了效率进行路径压缩
void unionset(int x,int y) { x=findset(x); y=findset(y); if(rank[x] > rank[y]) { p[x]=y; }else { p[y]=x; if(rank[x]==rank[y]) rank[x]++; } }
将较浅的合并到较深的以提高效率
转载于:https://www.cnblogs.com/tclan126/p/8488125.html
相关资源：数据结构—成绩单生成器