打卡第七十五天
2道中等题
并查集模板
题目：
思路：并查集+哈希
代码：
class UnionFind {vector<int> fa;vector<int> sz;
public:int cc;UnionFind(int n) : fa(n), sz(n, 0), cc(n) {iota(fa.begin(), fa.end(), 0);}int find(int x) {if (fa[x] != x) {fa[x] = find(fa[x]);}return fa[x];}void unite(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) return;// 按秩合并if (sz[rootX] < sz[rootY]) {fa[rootX] = rootY;}else if (sz[rootX] > sz[rootY]) {fa[rootY] = rootX;}else {fa[rootY] = rootX;sz[rootX]++;}cc--;}
};class Solution {
public:int numberOfComponents(vector<vector<int>>& properties, int k) {int n = properties.size(); // 将每个数组转换为集合去重vector<unordered_set<int>> sets(n);for (int i = 0; i < n; i++) {sets[i] = unordered_set<int>(properties[i].begin(), properties[i].end());}UnionFind uf(n);// 比较所有对 (i, j)for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 计算交集大小int cnt = 0;for (int x : sets[j]) {if (sets[i].contains(x)) {cnt++;}}if (cnt >= k) {uf.unite(i, j);}}}return uf.cc;}
};
耗时≈1.5小时 明天继续