fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. #define int long long
  5. #define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  6. const int MOD = 1e9 + 7 ;
  7.  
  8. int n  , m , ans = 1 ;
  9. int parent[1005], sz[1005] , bac[1005];
  10. bool visited[1005];
  11.  
  12. int Find(int u){
  13.     if(u == parent[u]) return u;
  14.     else return Find(parent[u]);
  15. }
  16.  
  17. void Union(int x , int y){
  18.     x = Find(x);
  19.     y = Find(y);
  20.     if(x == y) return  ;
  21.     else{
  22.         if(bac[x] > bac[y] || bac[x] == bac[y] && x < y){
  23.             parent[y] = x ;
  24.         }
  25.         else{
  26.             parent[x] = y ;
  27.         }
  28.     }
  29. }
  30.  
  31. void solve(){
  32.     cin >> n >> m ;
  33.  
  34.     for(int i = 1 ; i <= n ; i++){
  35.         parent[i] = i ;
  36.         sz[i] = 1;
  37.     }
  38.  
  39.     vector<pair<int,int> > v ;
  40.     for(int i = 1 ; i <= m ; i++){
  41.         int x , y ; cin >> x >> y ;
  42.         v.push_back({x , y});
  43.         bac[x]++;
  44.         bac[y]++;
  45.     }
  46.     // cout << ans << endl;
  47.  
  48.     for(auto edge : v){
  49.         Union(edge.first , edge.second);
  50.     }
  51.  
  52.     for(int i = 1 ; i <= n ; i++){
  53.         if(i == parent[i]){
  54.             cout << i << " ";
  55.         }
  56.     }
  57. }
  58.  
  59. signed main() {
  60.     faster(); 
  61.     int test = 1 ; 
  62.     // cin >> test ;
  63.     while(test--)   solve();
  64.     return 0;
  65. }
  66.  
  67.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
10 6
4 3
4 1
8 5
8 6
4 2
8 2
stdout
copy 
4 7 9 10
https://ideone.com/n9rkOl
language:
C++ (gcc 8.3)
created:
6 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!