Advertisement
Hamoudi30

Untitled

Aug 5th, 2021
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define SZ(v) ((int)(v).size())
  5. #define pb push_back
  6. const int N = 2e5+9;
  7. const int inf = 1e9+9;
  8.  
  9. vector<int> adj[N];
  10. bool vis[N];
  11.  
  12.  
  13. void DFS (int st_node) {
  14.     vis[st_node] = true;
  15.     for (int neg : adj[st_node]) {
  16.         if (!vis[neg]) {
  17.             DFS(neg);
  18.         }
  19.     }
  20. }
  21. /*
  22.     5 4
  23.     1 2
  24.     1 3
  25.     3 4
  26.     4 5
  27.  
  28.  
  29.     1 -> 2 3
  30.     2 -> 1
  31.     3 -> 1 4
  32.     4 -> 3 5
  33.     5 -> 4
  34.     6 ->
  35.  
  36.  */
  37.  
  38. void run () {
  39.     int n, m;
  40.     cin >> n >> m;
  41.     for (int i = 0; i < m; ++i) {
  42.         int u, v;
  43.         cin >> u >> v;
  44.         // undirected
  45.         // u -> v
  46.         // v -> u
  47.         adj[u].push_back(v);
  48.         adj[v].push_back(u);
  49.     }
  50.     DFS(1);
  51.     int count = 1;
  52.     for (int node = 1; node <= n; ++node) {
  53.         if (!vis[node]) {
  54.             count++;
  55.             DFS(node);
  56.         }
  57.     }
  58.     cout << count << '\n';
  59. }
  60. int main () {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(nullptr);
  63.     cout.tie(nullptr);
  64.     freopen("/home/hamoudi/clion/hello.in", "rt", stdin);
  65.     int tt;
  66.     tt = 1;
  67.     //    cin >> tt;
  68.     while (tt--)
  69.         run();
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement