并查集相关题目
简介
并查集(Union-Find-Set, UFS) 主要有两个功能:
- 将两个元素合并到一个集合中
- 判断两个元素在不在一个集合中
模板
路径压缩
// init
int fa[N];
for (int i{}; i < N; ++i) fa[i] = i;
// Find
function<int(int)> Find = [&](int u) {
return u == fa[u] ? u : fa[u] = Find(fa[u]);
};
// check
auto isSame = [&](int u, int v) { return Find(u) == Find(v); };
// join/Union
auto join = [&](int u, int v) {
u = Find(u), v = Find(v);
if (u == v) return;
fa[v] = u;
};
按秩合并
// init
int fa[N], rank[N];
for (int i{}; i < N; ++i) fa[i] = i, rank[i] = 1;
// Find
function<int(int)> Find = [&](int u) {
return u == fa[u] ? u : Find(fa[u]); // 不执行路径压缩
};
// check
auto isSame = [&](int u, int v) { return Find(u) == Find(v); };
// join/Union
auto join = [&](int u, int v) {
u = Find(u), v = Find(v);
if (u == v) return;
if (rank[u] <= rank[v])
fa[u] = v;
else
fa[v] = u;
// rank[u] <= rank[v] ? (fa[u] = v) : (fa[v] = u);
if (rank[u] == rank[v]) ++rank[v];
};
基础题
1971. 寻找图中是否存在路径;(直接深搜就可以, 但是作为一种方法还是要学一下并查集的)
class Solution { // DFS
public:
bool validPath(int n, vector<vector<int>>& edges, int source,
int destination) {
vector<vector<int>> g(n); // build graph
for (auto v : edges) {
int a{v[0]}, b{v[1]};
g[a].emplace_back(b);
g[b].emplace_back(a);
}
bool vs[n];
memset(vs, 0, sizeof(vs));
function<bool(int, int)> f = [&](int src, int dest) {
if (src == dest) return true;
vs[src] = true;
for (int i : g[src])
if (!vs[i] && f(i, dest)) return true;
return false;
};
return f(source, destination);
}
};
下面是并查集的代码, 快了不少!
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source,
int destination) {
constexpr int N = 2e5;
int fa[N];
for (int i{}; i < N; ++i) fa[i] = i;
function<int(int)> Find = [&](int u) {
return u == fa[u] ? u : fa[u] = Find(fa[u]);
};
auto isSame = [&](int u, int v) { return Find(u) == Find(v); };
auto join = [&](int u, int v) {
u = Find(u), v = Find(v);
if (u == v) return;
fa[v] = u;
};
for (auto v : edges) join(v[0], v[1]);
return isSame(source, destination);
}
};
// more simple
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source,
int destination) {
int fa[n];
for (int i{}; i < n; ++i) fa[i] = i;
function<int(int)> f = [&](int u) {
return u == fa[u] ? u : fa[u] = f(fa[u]);
};
for (auto e : edges) {
int a = f(e[0]), b = f(e[1]);
fa[a] = b;
}
return f(source) == f(destination);
}
};
按秩合并 :
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source,
int destination) {
int fa[n], rank[n]; // 按秩合并
for (int i{}; i < n; ++i) fa[i] = i, rank[i] = 1;
function<int(int)> Find = [&](int u) {
return u == fa[u] ? u : Find(fa[u]); // 不进行路径压缩
};
for (auto v : edges) {
int a = Find(v[0]), b = Find(v[1]);
if (rank[a] <= rank[b])
fa[a] = b;
else
fa[b] = a;
if (rank[a] == rank[b] && a != b) ++rank[b];
}
return Find(source) == Find(destination);
}
};
547. 省份数量; 剑指 Offer II 116. 省份数量;
需要记录连通块的大小
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int fa[n], ans{n};
for (int i{}; i < n; ++i)
fa[i] = i;
function<int(int)> find = [&](int u) {
return u == fa[u] ? u : fa[u] = find(fa[u]);
};
for (int i{}; i < n; ++i) {
for (int j{i + 1}; j < n; ++j) {
if (isConnected[i][j]) {
int u = find(i), v = find(j);
if (u != v) // 2 块可以合并为 1, 减少块数目
fa[v] = u, --ans;
}
}
}
return ans;
}
};
684. 冗余连接;剑指 Offer II 118. 多余的边;
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
int fa[n];
for (int i{}; i < n; ++i)
fa[i] = i;
function<int(int)> find = [&](int u) {
return u == fa[u] ? u : fa[u] = find(fa[u]);
};
for (auto e : edges) {
int a = e[0] - 1, b = e[1] - 1;
int u = find(a), v = find(b);
if (u != v) {
fa[v] = u;
} else
return e;
}
return {};
}
};
进阶题