PAT甲级1004题解——并查集思想改

佚名 5年前 (2019-10-09) 算法 1507人围观抢沙发百度已收录

题目分析：本题开始一直在考虑如何将每一个节点通过一种合适的数据结构存储起来（一对多的关系），最后发现借助并查集的思想可以用一个数组p，p[i]存放i节点的父节点，每次查询编号为i的节点属于第几层且判断是否有以该点位父元素的节点（判断该点是否为叶子节点，是则floor[对应层数]++）由于本题的图不存在环路，则借助这个p数组则能十分巧妙将整棵树存储下来，本题还借助了vis[]数组存放某个节点是否出现过（因为N个节点并不一定是有序出现的），mat数组存放下标为i时是否是叶子节点，floor[]数组i层的叶子节点的总数，本题需要额外注意的细节是：输入的N和M，M有可能是0，则由于根节点一定是1，所以第0层一定有一个叶子节点（1号节点本身），此外对于输入的每一行数据，每个节点的孩子节点数也有可能是0（0则代表是叶子节点，没有孩子节点）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int vis[105];        //记录i点是否是树上的节点 
 6 int floor[105];        //记录每一层的叶子节点的数量 1为0层 
 7 int p[105];            //记录i的父节点 
 8 int mat[105];         //存储是否有以i为父节点的节点 i
 9 int max_flo;
10 
11 void serach(int x){
12     int t = x;
13     int flo = 0;    //默认对于节点1来说属于0层 
14     while(p[x] != x){
15         x = p[x];
16         flo++;    
17     }
18     if(flo > max_flo) max_flo = flo; 
19     if(mat[t] == 0){//如果没有以这个节点为父节点的节点则代表这个节点是叶子节点 对应的层数叶节点数+1 
20         floor[flo]++;    
21     }     
22 }
23 
24 int main(){
25     int n, m;
26     while(scanf("%d", &n) != EOF){
27         if(n == 0) break;
28         scanf("%d", &m);
29         memset(floor, 0, sizeof(floor));
30         memset(vis, 0, sizeof(vis));
31         memset(mat, 0, sizeof(mat));
32         if(m == 0) floor[0]++;
33         max_flo = 0;                //初始化最深的层数 
34         for(int i = 1; i <= 100; i++) p[i] = i;
35         for(int i = 1; i <= m; i++){
36             int id, num;
37             scanf("%d%d", &id, &num);
38             vis[id] = 1;
39             if(num != 0) mat[id] = 1;
40             for(int j = 1; j <= num; j++){
41                 int x;
42                 scanf("%d", &x);
43                 p[x] = id;
44                 vis[x] = 1;
45             }
46         }
47         for(int i = 1; i <= 100; i++){
48             if(vis[i] == 1){        //对出现过的节点进行查询操作 
49                 serach(i);
50             }
51         }
52         for(int i = 0; i <= max_flo; i++){
53             if(i != 0) printf(" ");
54             printf("%d", floor[i]);
55         }
56         printf("\n");
57     }
58     return 0;
59 }