ka
user_8384735
c_cpp
3 years ago
994 B
6
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...