Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using std::vector;
- class DSU {
- public:
- explicit DSU(int n) : parent_(vector<int>(n, -1)),
- size_(vector<int>(n, 0)),
- whenCame_(vector<int>(n, 1)),
- numberOfUnits_(vector<int>(n, 1)) {} // TODO - точно ли 1 тут
- int Get(int v) {
- if (parent_[v] == -1) {
- return v;
- }
- return Get(parent_[v]);
- }
- bool CheckTwoElements(int u, int v) {
- return Get(v) == Get(u);
- }
- void Unit(int u, int v) {
- u = Get(u);
- v = Get(v);
- if (u != v) {
- if (size_[u] < size_[v]) { // v родитель u
- parent_[u] = v;
- size_[v] += size_[u];
- whenCame_[u] = numberOfUnits_[v];
- ++numberOfUnits_[v];
- } else { // u родитель v
- parent_[v] = u;
- size_[u] += size_[v];
- whenCame_[v] = numberOfUnits_[u];
- ++numberOfUnits_[u];
- }
- }
- }
- int GetNumberOfUnits(int u) {
- if (parent_[u] == -1) {
- return numberOfUnits_[u];
- }
- int uParent = Get(parent_[u]);
- return numberOfUnits_[uParent] - whenCame_[u] + numberOfUnits_[u];
- }
- private:
- vector<int> parent_;
- vector<int> size_;
- vector<int> whenCame_;
- vector<int> numberOfUnits_;
- };
- int main() {
- int n, m;
- std::cin >> n >> m;
- DSU dsu(n);
- for (int i = 0; i < m; ++i) {
- int type, x;
- std::cin >> type >> x;
- if (type == 1) {
- int y;
- std::cin >> y;
- dsu.Unit(x - 1, y - 1);
- } else if (type == 2) {
- int y;
- std::cin >> y;
- if (dsu.CheckTwoElements(x - 1, y - 1)) std::cout << "YES\n";
- else std::cout << "NO\n";
- } else if (type == 3) {
- std::cout << dsu.GetNumberOfUnits(x - 1) << "\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement