Advertisement
fooker

counts number of connected components (using dfs)

Nov 22nd, 2022
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. bool visited[10000]={0};
  5. int counter=0;
  6. vector <int> adj[10000];
  7. void dfs(int k){
  8.     visited[k]=true;
  9.     for (auto u:adj[k]){
  10.         if (!visited[u]){
  11.             dfs(u);
  12.         }
  13.     }
  14. }
  15. void connected(int x){
  16.     if (!visited[x]){
  17.         counter++;
  18.         dfs(x);
  19.     }
  20. }
  21. int main()
  22. {
  23.     int n,m;
  24.     cin>>n>>m;
  25.     for (int i=0; i<m; i++){
  26.         int x,y;
  27.         cin>>x>>y;
  28.         adj[x].push_back(y);
  29.         adj[y].push_back(x);
  30.     }
  31.     for (int i=1; i<=n; i++){
  32.         connected(i);
  33.     }
  34.     cout<<counter<<"\n";
  35. }
  36.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement