Re: [閒聊] 每日leetcode
1267. Count Servers that Communicate
## 思路
解法1 掃兩遍
第一次紀錄各行列的server個數
第二次檢查有無連接
解法2 UnionFind (row+col)
行跟列做union, rank是該組的server數量
把>1的加總
## Code
```cpp
class UnionFind {
public:
UnionFind(int size) {
rank_.resize(size, 0);
root_.resize(size, 0);
for (int i=0; i<size; ++i) {
root_[i] = i;
}
}
int findP(int x) {
if (root_[x] != x) {
return findP(root_[x]);
}
return x;
}
int unionP(int x, int y) {
int rx=findP(x), ry=findP(y);
if (rx == ry) {
++rank_[rx];
return false;
}
if (rank_[rx] < rank_[ry]) {
root_[rx] = root_[ry];
rank_[ry] += rank_[rx] + 1;
} else {
root_[ry] = root_[rx];
rank_[rx] += rank_[ry] + 1;
}
return true;
}
int getResult() {
int res = 0;
for (int i=0; i<root_.size(); ++i) {
if (root_[i] == i && rank_[i] > 1) {
res += rank_[i];
}
}
return res;
}
private:
vector<int> root_;
vector<int> rank_;
int count_ = 0;
};
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int lenR=grid.size(), lenC=grid[0].size();
UnionFind uf(lenR + lenC);
for (int r=0; r<lenR; ++r) {
for (int c=0; c<lenC; ++c) {
if (grid[r][c] == 0) continue;
uf.unionP(r, lenR+c);
}
}
return uf.getResult();
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 86.48.12.74 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737636036.A.017.html
推
01/23 20:40,
10月前
, 1F
01/23 20:40, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1301 之 1552 篇)：