题目：共同好友圈子（朋友圈数量）

题目描述

有  n  个用户，编号从  0  到  n-1 。

给你一个二维数组  friendships ，其中

 friendships[i] = [u, v]  表示用户  u  和用户  v  是直接好友。

好友关系满足：

- 如果  u  与  v  是好友， v  与  w  是好友，则  u  与  w  属于同一个朋友圈。

​

- 朋友圈是最大的好友连通集合。

请你计算：

总共有多少个不同的朋友圈？

#include <vector>

using namespace std;

class DSU {

private:

vector<int> parent;

public:

DSU(int n) {

parent.resize(n);

for (int i = 0; i < n; ++i)

parent[i] = i;

}

int find(int x) {

if (parent[x] != x)

parent[x] = find(parent[x]);

return parent[x];

}

void unite(int x, int y) {

x = find(x);

y = find(y);

if (x != y)

parent[y] = x;

}

};

class Solution {

public:

int findCircleNum(int n, vector<vector<int>>& friendships) {

DSU dsu(n);

for (auto& e : friendships) {

dsu.unite(e[0], e[1]);

}

int cnt = 0;

for (int i = 0; i < n; ++i) {

if (dsu.find(i) == i)

cnt++;

}

return cnt;

}

};