https://codeforces.com/problemset/problem/277/A
It presents a problem that we need to make all element connected, it can be solved by using dsu.
I didn't use my dsu model and write a simple version of Dsu.
class DSU{
public:
DSU(int m): size_(m){
fa_.resize(m);
std::iota(fa_.begin(), fa_.end(), 0);
}
int findSet(int x){
return fa_[x] == x ? x : fa_[x] = findSet(fa_[x]);
}
bool isSameSet(int x, int y){
return findSet(x) == findSet(y);
}
bool unionSet(int u, int v){
u = findSet(u);
v = findSet(v);
if (u == v){
return false;
}
return fa_[u] = v, true;
}
private:
vector<int> fa_;
int size_;
};
void solve(){
int n, m;
cin >> n >> m;
DSU dsu(m + 1);
vector<int> vis(m + 1);
int ans = 0;
for (int i = 0; i < n; ++i){
int k;
cin >> k;
if (!k){
ans ++;
}
int pre = -1;
while (k --){
int t;
cin >> t;
if (pre != -1){
dsu.unionSet(pre, t);
}
pre = t;
vis[t] = true;
}
}
for (int i = 1; i <= m; ++i){
for (int j = i + 1; j <= m; ++j){
if (vis[i] && vis[j] && dsu.isSameSet(i, j) == false){
dsu.unionSet(i, j);
ans ++;
}
}
}
cout << ans << '\n';
}
标签:pre,return,int,dsu,Languages,fa,findSet,Learning
From: https://www.cnblogs.com/yxcblogs/p/18059768