fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int oo = 1e9 + 7;
  5. const int N = 1e5 + 7;
  6.  
  7. int n,m;
  8. bool vis[N];
  9. vector<int>v[N];
  10.  
  11. void bfs(int s){
  12.     queue<int>q;
  13.     q.push(s);
  14.  
  15.     vis[s] = 1;
  16.  
  17.     while(!q.empty()){
  18.         int u = q.front();
  19.         q.pop();
  20.  
  21.         for(auto x : v[u]){
  22.             if(!vis[x]){
  23.                 vis[x] = 1;
  24.                 q.push(x);
  25.             }
  26.         }
  27.     }
  28. }
  29.  
  30. signed main(){
  31.     ios_base::sync_with_stdio(0); cin.tie(0);
  32.  
  33.     cin >> n >> m;
  34.  
  35.     for(int i=1; i <= m; i++){
  36.         int a,b; cin >> a >> b;
  37.         v[a].push_back(b);
  38.         v[b].push_back(a);
  39.     }
  40.  
  41.     int cnt = 0;
  42.  
  43.     for(int i=1; i<=n; i++){
  44.         if(!vis[i]){
  45.             cnt++;
  46.             bfs(i);
  47.         }
  48.     }
  49.  
  50.     cout << cnt;;
  51. }
  52.  
Success #stdin #stdout 0.01s 5916KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uV5JUI
language:
C++14 (gcc 8.3)
created:
4 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!