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();
}
};
```