LeetcodeLCR 116. 省份数量
文章目录
- 题目
- 原题链接
- 思路
- C++代码
题目
原题链接
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;}
};