fork(5) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define dbg(x) cout << #x << " : " << x << endl
  5. #define rep(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define maxn 100005
  7. vector<ll> edges[maxn];
  8. ll dau[maxn];
  9. ll n, m;
  10. void dfs(ll source)
  11. {
  12.     dau[source] = 1;
  13.     stack<ll> st;
  14.     st.push(source);
  15.     while (!st.empty())
  16.     {
  17.         ll p = st.top();
  18.         st.pop();
  19.         for (auto v : edges[p])
  20.         {
  21.             if (dau[v] == 1)
  22.                 continue;
  23.             dau[v] = 1;
  24.             st.push(v);
  25.         }
  26.     }
  27. }
  28. int main()
  29. {
  30.     // freopen("input.txt","r",stdin);
  31.     // freopen("output.txt","w",stdout);
  32.     cin >> n >> m;
  33.     for (ll i = 0; i < m; i++)
  34.     {
  35.         ll u, v;
  36.         cin >> u >> v;
  37.         u--, v--;
  38.         edges[u].push_back(v);
  39.         edges[v].push_back(u);
  40.     }
  41.     ll dem = 0;
  42.     for (ll i = 0; i < n; i++)
  43.     {
  44.         if (dau[i] == 0)
  45.         {
  46.             dem++;
  47.             dfs(i);
  48.         }
  49.     }
  50.     cout << dem << '\n';
  51.     return 0;
  52. }
Success #stdin #stdout 0.01s 5864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/PzWvBO
language:
C++14 (gcc 8.3)
created:
3 years 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!