并查集裸题
求省份数量就相当于求并查集森林的数量
以根节点为例 根节点的特性就是father[i] == i
其余的按照题干走
class Solution {
public:
class UnionSet {
public:
int *father, n;
UnionSet(int n) : n(n) {
father = new int[n + 1];
for (int i = 0; i <= n; i++) {
father[i] = i;
}
}
int get(int x) {
return father[x] == x ? x : get(father[x]);
}
void merge(int a, int b) {
father[get(a)] = get(b);
}
};
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
UnionSet u(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (isConnected[i][j]) u.merge(i, j);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += (u.get(i) == i);
}
return ans;
}
};和上个题一样的思路
我们将岛屿们联通起来
然后进行一个遍历
找根节点的数量就是岛屿的数量
这里需要一个二维转一维的小技巧用来确定每个节点的编号
#define ind(i, j) ((i) * m + (j))
class Solution {
public:
class UnionSet {
public :
int *father, n;
UnionSet(int n) : n(n) {
father = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
father[i] = i;
}
}
int get(int x) {
if (father[x] == x) return x;
int root = get(father[x]);
father[x] = root;
return root;
}
void merge(int a, int b) {
father[get(a)] = get(b);
}
};
int numIslands(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
UnionSet u(n * m);
#define ind(i, j) ((i) * m + (j))
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '0') continue;
if (i > 0 && grid[i - 1][j] == '1') u.merge(ind(i, j), ind(i - 1, j));
if (j > 0 && grid[i][j - 1] == '1') u.merge(ind(i, j), ind(i, j - 1));
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans += (grid[i][j] == '1' && u.get(ind(i, j)) == ind(i, j));
}
}
return ans;
}
};这里的a == b就是一种连通性
因为可以通过两个等式从而推断出三者相等来
但是不等号就没这样的传递性
所以呢就遍历两次
第一次解决连通性
第二次判断a b是否真正连通
如果有!=就不是 就和连通矛盾了
class Solution {
public:
class UnionSet {
public :
int *father, n;
UnionSet(int n) : n(n) {
father = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
father[i] = i;
}
}
int get(int x) {
if (father[x] == x) return x;
int root = get(father[x]);
father[x] = root;
return root;
}
void merge(int a, int b) {
father[get(a)] = get(b);
return ;
}
};
bool equationsPossible(vector<string>& equations) {
UnionSet u(26);
// 先处理等式
// 吧他们都联通起来
for (auto s : equations) {
if (s[1] == '!') continue;
int a = s[0] - 'a';
int b = s[3] - 'a';
u.merge(a, b);
}
for (auto s : equations) {
if (s[1] == '=') continue;
int a = s[0] - 'a';
int b = s[3] - 'a';
if (u.get(a) == u.get(b)) return false;
}
return true;
}
};vector<int> findRedundantConnection(vector<vector<int>>& edges) {
UnionSet u(edges.size());
for (auto e : edges) {
int a = e[0];
int b = e[1];
// 如果a b是联通的就直接返回这个边
if (u.get(a) == u.get(b)) return e;
u.merge(a, b);
}
return vector<int>();
}首先 n 个电脑至少要n - 1个线
所以如果链接数量连n - 1都不够肯定连通不了
再一个稍微思考一下就能知道
我们按照题意联通完成之后，假设有x个集合
是不是x - 1根线就能全部连通？
所以返回集合数量 - 1即可
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) return -1;
UnionSet u(n);
for (auto x : connections) {
int a = x[0];
int b = x[1];
u.merge(a, b);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += (u.get(i) == i);
}
return ans > n - 1 ? -1 : ans - 1;
}连续的序列是1, 2, 3, 4这样的
这其中有什么连通性呢？
对于n来说
如果我们找到n - 1和n + 1
把他们加到一个集合里
并且记录下集合的长度
这里注意的是对于数组来说
我们是不能merge数组的元素的！
因为没办法通过元素找下标，但是可以通过下标找元素
所以用哈希表做一个数字到下标的映射
class Solution {
public:
class UnionSet {
public :
// 新增cnt用来记录元素数量
int *father, *cnt, n;
UnionSet(int n) : n(n) {
father = new int[n + 1];
cnt = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
father[i] = i;
cnt[i] = 1;
}
}
int get(int x) {
if (father[x] == x) return x;
int root = get(father[x]);
father[x] = root;
return root;
}
void merge(int a, int b) {
if (get(a) == get(b)) return ;
// 节点调整一定要在计算数量之后
// 因为merge完成之后节点数量就都变了
// 我们所想要的是之前的节点数量
cnt[get(b)] += cnt[get(a)];
father[get(a)] = get(b);
return ;
}
};
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> ind;
UnionSet u(nums.size());
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
if (ind.find(x) != ind.end()) continue;
// 表示找到了x - 1 可以加到集合中去
if (ind.find(x - 1) != ind.end()) {
u.merge(i, ind[x - 1]);
}
if (ind.find(x + 1) != ind.end()) {
u.merge(i, ind[x + 1]);
}
ind[x] = i;
}
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
if (u.get(i) == i && u.cnt[i] > ans) ans = u.cnt[i];
}
return ans;
}
};class Solution {
public:
// 既然同行或者同列的石头是联通的
// 所以一个集合可以去掉n - 1个
// 那么就是求最后的集合数量
// 一个集合去n - 1 能剩一个
// 最后可以移除的就是总节点数 - 集合数
class UnionSet {
public :
int *father, n;
UnionSet(int n) : n(n) {
father = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
father[i] = i;
}
}
int get(int x) {
if (father[x] == x) return x;
int root = get(father[x]);
father[x] = root;
return root;
}
void merge(int a, int b) {
father[get(a)] = get(b);
return ;
}
};
int removeStones(vector<vector<int>>& stones) {
UnionSet u(stones.size());
// 依然是要存下标
// ind_x存x轴出现的第一个石头的编号
unordered_map<int, int> ind_x, ind_y;
for (int i = 0; i < stones.size(); i++) {
int x = stones[i][0];
int y = stones[i][1];
// 去ind中找下标
// 有下标的表示这个石头有相同的行或者列
// 可以merge
if (ind_x.find(x) != ind_x.end()) {
u.merge(i, ind_x[x]);
}
if (ind_y.find(y) != ind_y.end()) {
u.merge(i, ind_y[y]);
}
ind_x[x] = i;
ind_y[y] = i;
}
int ans = 0;
for (int i = 0; i < stones.size(); i++) {
ans += (u.get(i) == i);
}
return stones.size() - ans;
}
};class Solution {
public:
// 思路：
// 既然位置是可以互换的 那就是可互换的位置上的字母是可以单独拎出来
// 就将这些连通之后排最小的字典序
// 不过排序是要分组排序(heap)
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
UnionSet u(s.size());
// 完成联通的操作其实很简单
for (auto p : pairs) {
int i = p[0];
int j = p[1];
u.merge(i, j);
}
priority_queue<char, vector<char>, greater<char>> h[s.size()];
// 字符压入小顶堆 为了排序
for (int i = 0; i < s.size(); i++) {
// 相连通的都压入一个堆
h[u.get(i)].push(s[i]);
}
string ret = "";
for (int i = 0; i < s.size(); i++) {
// 每次轮询这些堆
// 每次拿一个堆的堆顶出来带走
ret += h[u.get(i)].top();
h[u.get(i)].pop();
}
return ret;
}
};因为我知道我可以赢你，就相当于你会输给我
那么你会赢别人的话，我就会输给那个人
你输给别人我就和那个人平手
你和那人平手我就赢了
这本质上也是一种带权的并查集关系
假设从✌️开始
✌️->✊->✋->✌️->✊->✋->✌️->✊
在这个路径上假设每步的步长为1
x到y的所有权值和对3取余就是输赢的结果
从x->y逆向推导y->x
因为是%3 所以加上或者减去k倍的3对结果无影响
