tien_noob

Count Connected Component in undirected graph with adj list

Feb 23rd, 2021 (edited)
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <cmath>
  6. #include <climits>
  7. #include <queue>
  8. using namespace std;
  9. const int N = 8e5, M = 4e6;
  10. int n, m, Trace[N+1], x, y;
  11. vector<vector<int>> Adj;
  12. void read()
  13. {
  14.    cin >> n >> m;
  15.    Adj.resize(n + 1);
  16.    for (int i = 1; i <= m; ++ i)
  17.    {
  18.        cin >> x >> y;
  19.        Adj[x].push_back(y);
  20.        Adj[y].push_back(x);
  21.    }
  22. }
  23. void DFS(int u)
  24. {
  25.     Trace[u] = -1;
  26.     for (int v : Adj[u])
  27.     {
  28.         if (Trace[v] == 0)
  29.         {
  30.             Trace[v] = u;
  31.             DFS(v);
  32.         }
  33.     }
  34. }
  35. void solve()
  36. {
  37.    int cnt = 0;
  38.    for (int i = 0; i < n; ++ i)
  39.    {
  40.        if (Trace[i] == 0)
  41.        {
  42.            ++cnt;
  43.            DFS(i);
  44.        }
  45.    }
  46.    cout << cnt;
  47. }
  48. int main()
  49. {
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(nullptr);
  52.     //freopen ("TESTCODE.INP", "r", stdin);
  53.     read();
  54.     solve();
  55. }
  56.  
Add Comment
Please, Sign In to add comment