你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ,其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。返回 图中已连接分量的数目 。
链接:https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/description/
class UnionFind {
public:
int* father;
int cnt;
UnionFind(int n) {
father = new int[n];
for (int i = 0; i < n; ++i) {
father[i] = i;
}
cnt = n;
}
int find(int x) {
int j = x;
while (father[j] != j) {
j = father[j];
}
while (j != x) {
int tmp = father[x];
father[x] = j;
x = tmp;
}
return j;
}
void connect(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) {
father[fa] = fb;
cnt--;
}
}
int getCnt() {
return cnt;
}
};
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
UnionFind uf(n);
for (auto& e: edges) {
uf.connect(e[0], e[1]);
}
return uf.getCnt();
}
};
给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组A. 初始二维矩阵全0. 二元数组A内的k个元素代表k次操作, 设第i个元素为 (A[i].x, A[i].y)
, 表示把二维矩阵中下标为A[i].x行A[i].y列的元素由海洋变为岛屿. 问在每次操作之后, 二维矩阵中岛屿的数量. 你需要返回一个大小为k的数组.
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class UnionFind {
public:
int* father;
int cnt = 0;
UnionFind(int n) {
father = new int[n];
for (int i = 0; i < n; ++i) {
// father[i] = i;
father[i] = -1;
}
}
int find(int x) {
int j = x;
while (father[j] != j) {
j = father[j];
}
while (x != j) {
int tmp = father[x];
father[x] = j;
x = tmp;
}
return j;
}
void connect(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) {
father[fa] = fb;
cnt--;
}
}
bool notSea(int n) {
return father[n] != -1;
}
void insert(int n) {
if (!notSea(n)) {
father[n] = n;
cnt++;
}
}
int get() {
return cnt;
}
};
class Solution {
public:
/**
* @param n: An integer
* @param m: An integer
* @param operators: an array of point
* @return: an integer array
*/
vector<int> numIslands2(int n, int m, vector<Point> &operators) {
UnionFind uf(n * m);
vector<int> rec;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
for (auto& op: operators) {
int point = op.x * m + op.y;
uf.insert(point);
for (int d = 0; d < 4; ++d) {
int newPoint = (op.x + dx[d]) * m + op.y + dy[d];
if (op.x + dx[d] >= 0 && op.x + dx[d] < n && op.y + dy[d] >= 0
&& op.y + dy[d] < m && uf.notSea(newPoint)) {
uf.connect(point, newPoint);
}
}
rec.push_back(uf.get());
}
return rec;
}
};
【721. 账户合并】
链接:https://leetcode.cn/problems/accounts-merge/description/
class UnionFind {
public:
map<string, string> father;
UnionFind (vector<vector<string>>& accounts) {
for (auto ac: accounts)
{
for (int i = 1; i < ac.size(); ++i)
{
if (father.find(ac[i]) == father.end())
{
father[ac[i]] = ac[i];
}
if (i != 1) connect(ac[i], ac[1]);
}
}
}
void connect(string a, string b) {
string fa = find(a);
string fb = find(b);
if (fa != fb)
{
father[fa] = fb;
}
}
string find(string a) {
string x = a;
while (father[a] != a)
{
a = father[a];
}
while (x != a)
{
string tmp = father[x];
father[x] = a;
x = tmp;
}
return a;
}
};
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n = accounts.size();
UnionFind uf(accounts);
map<string, string> name;
vector<vector<string>> res;
map<string, set<string>> mapRes;
for (auto ac: accounts)
{
for (int i = 1; i < ac.size(); ++i)
{
name[ac[i]] = ac[0];
string f = uf.find(ac[i]);
if (mapRes[f].find(ac[i]) == mapRes[f].end())
mapRes[f].insert(ac[i]);
}
}
for (auto t: mapRes)
{
vector<string> tmpRes;
tmpRes.push_back(name[t.first]);
vector<string> emails;
emails.assign(t.second.begin(), t.second.end());
tmpRes.insert(tmpRes.end(), emails.begin(), emails.end());
res.push_back(tmpRes);
}
return res;
}
};