Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("nunta.in");
- ofstream fout("nunta.out");
- const int N_MAX = 2e4 + 5;
- int n, m, groups;
- vector <int> unions[N_MAX], root, sums;
- void union_2(vector <int> &a, vector <int> &b) {
- vector <int> *x, *y;
- if (a.size() >= b.size()) {
- x = &a;
- y = &b;
- } else {
- x = &b;
- y = &a;
- }
- int index = root[(*x)[0]];
- for (const auto &i : (*y)) {
- (*x).emplace_back(i);
- root[i] = index;
- }
- (*y).clear();
- }
- int main() {
- fin >> n >> m;
- root.resize(n + 1);
- for (int i = 1; i <= n; ++i) {
- unions[i].emplace_back(i);
- root[i] = i;
- }
- while (m--) {
- int x, y;
- fin >> x >> y;
- int rx = root[x], ry = root[y];
- if (rx != ry) {
- union_2(unions[rx], unions[ry]);
- }
- }
- for (int i = 1; i <= n; ++i) {
- int size_group = (int) unions[i].size();
- if (size_group > 1) {
- ++groups;
- }
- }
- fout << groups;
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement