【PTA】7-4 朋友圈（C++ * 并查集思想）代码实现 一点反思

本文主要是介绍【PTA】7-4 朋友圈（C++ * 并查集思想）代码实现 一点反思，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 题目如下：

AC代码如下（参考PTA 7-2 朋友圈（25 分）_处理微信消息pta-CSDN博客）

#include<bits/stdc++.h>
using namespace std;
#define sz 30005
typedef struct node{int rk, fa;
}Node;
Node tree[sz];
void Init(Node t[], int n)
{for(int i=1; i<=n; i++){t[i].fa = i;t[i].rk = 0;		}
}int Find_fa(int a)
{if(tree[a].fa == a){return a;}return Find_fa(tree[a].fa);
}void Union(int a, int b)
{int m = Find_fa(a);int n = Find_fa(b);if(tree[m].rk < tree[n].rk){tree[m].fa = n;}else{tree[n].fa = m;if(tree[m].rk == tree[n].rk) tree[m].rk++;}
}int main()
{int n, m;cin>>n>>m;Init(tree, n);int num, help[sz]={0};for(int i=0; i<m; i++){cin>>num>>help[0];for(int j=1; j<num; j++){cin>>help[j];Union(help[j-1], help[j]);}}int max = 0, cal[sz] = {0};for(int i=1; i<=n; i++){int father = Find_fa(i);cal[father]++;max = cal[father] > max ? cal[father] : max;}cout<<max;
}

一点反思：

1. 将大问题拆成小问题：先找父节点，最后再总体遍历一次计算最大值。

2. 关于更新父亲结点：不寻求在每一次更新节点的时候就能将所有相关节点的父亲结点都给统一更新好，而是两个两个建立父子关系，最后统一用FInd_fa函数来查找父节点。

~希望对你有启发~

这篇关于【PTA】7-4 朋友圈（C++ * 并查集思想）代码实现 一点反思的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---