Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int32_t parent[100000];
- int32_t ans = 0;
- void make_set(int v) {
- parent[v] = v;
- }
- int find_set(int v) {
- if (v == parent[v])
- return v;
- return parent[v] = find_set(parent[v]);
- }
- void union_sets(int a, int b) {
- a = find_set(a);
- b = find_set(b);
- if (a != b)
- {
- parent[b] = a;
- ans -= 1;
- }
- }
- const int blocksize = 2000;
- int main()
- {
- int32_t n = 0, m = 0;
- auto fin = fopen("input.bin", "rb");
- auto fout = fopen("output.bin", "wb");
- fread(reinterpret_cast<char *>(&n), 4, 1, fin);
- fread(reinterpret_cast<char *>(&m), 4, 1, fin);
- ans = n;
- for (int i = 0; i < n; ++i)
- {
- make_set(i);
- }
- int32_t a[blocksize];
- for (int i = 0; i < m; i += blocksize)
- {
- fread(reinterpret_cast<char *>(&a), 4, min(blocksize, (m - i) * 2), fin);
- for (int j = 0; j < min(blocksize, (m - i) * 2); j += 2)
- {
- union_sets(a[j], a[j + 1]);
- }
- }
- fwrite(&ans, 4, 1, fout);
- fclose(fin);
- fclose(fout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement