fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define endl "\n"
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define yes cout<<"YES"<<"\n"
  7. #define no cout<<"NO"<<"\n"
  8. const ll N = 1e5+10; 
  9. const ll INF = 1e9+10;
  10. using namespace std;
  11.  
  12. ll parent[N];
  13. ll size[N];
  14.  
  15. void make(ll v) {
  16.     parent[v] = v;
  17.     size[v] = 1;
  18. }
  19.  
  20. ll find(ll v) {
  21.     if(parent[v] == v) return v;
  22.     return parent[v] = find(parent[v]);
  23. }
  24.  
  25. void Union(ll a, ll b) {
  26.     a = find(a);
  27.     b = find(b);
  28.     if(a != b) {
  29.         // Union by size
  30.         if(size[a] < size[b])
  31.             swap(a,b);
  32.         parent[b] = a;
  33.         size[a] += size[b];
  34.     }
  35. }
  36.  
  37. int main() {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(0);
  40.     // code
  41.     ll n, k; cin >> n >> k;
  42.     for(ll i = 1; i <= n; i++) {
  43.         make(i);
  44.     }
  45.     while(k--) {
  46.         ll u, v; cin >> u >> v;
  47.         Union(u, v);
  48.     }
  49.     // print the value of connected components
  50.     for(ll i = 1; i <= n; i++) {
  51.         if(find(i) == i) {
  52.             cout << "Component Root: "
  53.             << i << ", size: " << size[i] << endl;
  54.         }
  55.     }
  56. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
7 4
1 2
2 3
4 5
6 7
stdout
copy 
Component Root: 1, size: 3
Component Root: 4, size: 2
Component Root: 6, size: 2
https://ideone.com/N4OYLz
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!