Connected Components of graph|| code: CC

 

Problem

Given a undirected graph find the number of connected components.

Input

First line of the input is 't'- number of test case.
Followed by N, the number of vertices (Numbered 0 to N-1).
Followed by 'e' number of edges.
Followed by description of 'e' edges in the form 'a b' I.e. an edge exist between vertex a and b.
Constraints:
T=10
2 <= N <= 100000
0 <= e <= N/2

Output

One line per test case, number of connected components in the graph.

Example

Input:
2
4
2
0 1
0 2
8
0


Output:
2
8

solution:

#include <bits/stdc++.h>

using namespace std;

void dfs(int i , vector<bool>&visited , vector<int>graph[])

{

    visited[i] = true;

    for(int k : graph[i] )

    {

        if(!visited[k])

        {

            dfs(k, visited , graph);

        }

    }

}

int main() {

     int t;

     cin >> t;

     while(t--)

     {

         int n ; 

         cin >> n;

         int e;

         cin >> e;

         vector<int>graph[n];

         if(e != 0)

         {

         for(int i = 0 ; i < e ; i++)

         {

            int a , b ;

            cin >> a >> b;

            graph[a].push_back(b);

            graph[b].push_back(a);

            

         }

         }

         vector<bool>visited(n , false);

         int count =0;

         for(int i = 0 ; i < n ; i++)

         {

             if(!visited[i])

             {

                count++;

                dfs(i , visited , graph);

             }

         }

         cout << count << "\n";

         

     }

return 0;

}