Advertisement
fooker

counts number of connected components (using dfs + t testcases)

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