題目

原題鏈接

LCR 116. 省份數(shù)量

思路

利用并查集的思想，將連接的誠實放在一個集合當中，最后遍歷并查集數(shù)組判斷有幾顆樹

• 初始化一個并查集；
• 將連通的城市合并；
• 統(tǒng)計并查集中樹的個數(shù)；

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; }}}// 統(tǒng)計并查集中集合的個數(shù)int n = 0;for (const int& e : ufs) {if (e < 0)n++;}return n;}
};