Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 1e5 + 10;
- array<int, MAXN> pai, sub;
- int qComp = 0;
- int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
- void une(int x, int y)
- {
- x = find(x); y = find(y);
- if (x == y) return;
- if (sub[x] < sub[y]) swap(x, y);
- pai[y] = x; sub[x] += sub[y];
- --qComp;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N, M; cin >> N >> M;
- vector<pair<int, int>> edges(M);
- for (auto &[x, y] : edges) cin >> x >> y;
- for (int i = 1; i <= N; i++) {pai[i] = i; sub[i] = 1;}
- qComp = N;
- vector<int> resp;
- reverse(edges.begin(), edges.end());
- for (auto [x, y] : edges)
- {
- une(x, y);
- //cout << qComp << '\n'; cuidado! estamos fazendo ao contrario!
- resp.push_back(qComp);
- }
- reverse(resp.begin(), resp.end());
- for (auto x : resp) cout << x << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
