fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4.  
  5. int parent[N],sz[N];
  6.  
  7. void make(int v){
  8. parent[v] = v;
  9. sz[v]=1;
  10. }
  11.  
  12. int find(int v){
  13. if(v == parent[v]) return parent[v];
  14. //path compression
  15.  parent[v]=find(parent[v]);
  16. return parent[v];
  17.  
  18. }
  19.  
  20. void Union(int a, int b){
  21.     a=find(a);
  22.     b=find(b);
  23.     if(a!=b){
  24.         //union by size
  25.         if(sz[a]<sz[b])swap(a,b);
  26.         parent[b]=a;
  27.         sz[a]+=sz[b];
  28. }
  29. }
  30. int main(){
  31.  
  32. int n,k;
  33. cin>>n>>k;//number of nodes and edges
  34. for(int i=1;i<=n;i++){
  35.     make(i);
  36. }
  37. while(k--)
  38. {
  39.     int u,v;
  40.     cin>>u>>v;
  41.     Union(u,v);
  42. }
  43. int connected_components=0;
  44. for(int i=1;i<=n;i++){
  45.     if(find(i)==i)connected_components++;
  46. }
  47. cout<<connected_components<<endl;
  48.  
  49.  
  50. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
4 3
1 2
3 1
3 4
stdout
copy 
1
https://ideone.com/mPA8W4
language:
C++ (gcc 8.3)
created:
11 hours 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!