你有一个包含 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;}};
关于互联网持续学习圈
