题目

原题链接

LCR 116. 省份数量

思路

利用并查集的思想，将连接的诚实放在一个集合当中，最后遍历并查集数组判断有几颗树

• 初始化一个并查集；
• 将连通的城市合并；
• 统计并查集中树的个数；

C++代码

class Solution 
{
public:int findCircleNum(vector<vector<int>>& isConnected) {// 初始化并查集vector<int> ufs(isConnected.size(), -1); auto findRoot = [&ufs](int x){int parent = x;while (ufs[parent] >= 0) parent = ufs[parent];return parent;};for(int i = 0; i < isConnected.size(); i++)for(int j = 0; j < isConnected[0].size(); j++){// 是否连通if(isConnected[i][j] == 1){int root1 = findRoot(i);int root2 = findRoot(j);// 合并if (root1 != root2) {ufs[root1] += ufs[root2];ufs[root2] = root1; }}}// 统计并查集中集合的个数int n = 0;for (const int& e : ufs) {if (e < 0)n++;}return n;}
};