fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. // Path option optimization : Tối ưu nén đường
  4. // Tối ưu gộp kích thước
  5. int n ;
  6. const int maxn = 1005;
  7. int parent[1000001],sz[maxn];
  8.  
  9. void ktao(){
  10.     cin >> n ;
  11.     for(int i = 1 ; i <= n ; i++){
  12.         parent[i] = i;
  13.     }
  14. }
  15.  
  16. int Find(int u){
  17.     while(u != parent[u]){
  18.         u = parent[u];
  19.     }
  20.     return u;
  21. }
  22. /*
  23. int Find(int u){
  24.     if(u == parent[u]) return u ;
  25.     else return parent[u] = Find(parent[u]);
  26. }
  27. */
  28.  
  29. bool Union(int u,int v){
  30.     u = Find(u);
  31.     v = Find(v);
  32.     if(u == v){
  33.         return false;
  34.     }
  35.     else{
  36.         if(u < v) parent[v] = u;
  37.         else parent[u] = v;
  38.         return true;
  39.     }
  40. }
  41. /*bool Union(int u,int v){
  42.     u = Find(u);
  43.     v = Find(v);
  44.     if(u == v) return false;
  45.     if(sz[u] < sz[v]){
  46.         swap(u,v);
  47.     }
  48.     sz[u] += sz[v];
  49.     parent[v] = u;
  50.     return true;
  51. }*/
  52. int main(){
  53.     ktao();
  54.     int m; cin >> m ;
  55.     for(int i = 1 ; i <= m ; i++){
  56.         int x,y;
  57.         cin >> x >> y;
  58.         Union(x,y);
  59.     }
  60.     set<int> se;
  61.     for(int i = 1 ; i <= n ; i++){
  62.         se.insert(parent[i]);
  63.     }
  64.     cout << se.size();
  65. }
  66.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
5 4
4 1
2 1
3 2
4 3
stdout 
2
https://ideone.com/lqPUi6
[Graph]. Bài 13. Đếm số thành phần liên thông
language:
C++ (gcc 8.3)
created:
14 days 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!