Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int a[100000], b[100000];
- int fnd(int i)
- {
- if (i == b[i])
- return i;
- else
- return b[i] = fnd(b[i]);
- }
- int main()
- {
- int n, m, k, ii, jj, ans = 0, fii, fjj;
- cin >> n >> m >> k;
- k--;
- if (k == 0)
- ans = n;
- for (int i = 0; i < n; i++)
- b[i] = i;
- for (int i = 0; i < m; i++)
- {
- cin >> ii >> jj;
- ii--;
- jj--;
- fii = fnd(ii);
- fjj = fnd(jj);
- if (fii != fjj)
- {
- b[fjj] = fii;
- if (a[fii] < k && a[fii] + a[fjj] + 1 >= k)
- ans++;
- if (a[fjj] >= k)
- ans--;
- a[fii] += a[fjj] + 1;
- a[fjj] = 0;
- }
- cout << ans << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement