ka
user_8384735
c_cpp
3 years ago
994 B
12
Indexable
// Association for Control Over Minds.cpp
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using namespace std;
using ll = long long;
using um = unordered_map<int, unordered_set<int>>;
const int N = 500005;
int p[N], psize[N];
int t, n, ans, y;
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void unionset(int a, int b){
a = find(a), b = find(b);
//if (psize[a] >= psize[b]) swap(a, b);
psize[a] += psize[b];
p[b] = a;
}
int main(){
cin >> t;
for (int i = 1; i < N; i++) p[i] = i, psize[i] = 1;
while (t--){
cin >> n;
um tmp = um{};
for (int i = 0; i < n; i++){
cin >> y;
int x = find(y);
tmp[x].insert(y);
}
for (auto x : tmp) {
if (x.second.size() != psize[x.first]) n = -1;
n -= psize[x.first];
}
if (!n){
ans++;
for (auto x = tmp.begin(); ++x != tmp.end();)
unionset(x->first, tmp.begin()->first);
}
}
cout << ans << endl;
return 0;
}Editor is loading...