Created
October 31, 2020 20:02
-
-
Save Ch-sriram/82f575fef54ebf1c4b5c1ab019f59ebe to your computer and use it in GitHub Desktop.
Number of Connected Components [TC: O(V+E); SC: O(V)]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <vector> | |
#include <iostream> | |
#include <algorithm> | |
using namespace std; | |
void DFSRec(vector<int> *G, int src, vector<bool> &visited) { | |
visited[src] = true; | |
for(int u: G[src]) | |
if(!visited[u]) | |
DFSRec(G, u, visited); | |
} | |
int DFSDisconnected(vector<int> *G, const int V) { | |
int count = 0; | |
vector<bool> visited(V, false); | |
for(int i = 0; i < V; ++i) | |
if(!visited[i]) | |
++count, DFSRec(G, i, visited); | |
return count; | |
} | |
void addEdge(vector<int> *G, int u, int v) { | |
G[u].push_back(v); | |
G[v].push_back(u); | |
} | |
int main() { | |
int t; cin >> t; | |
while(t--) { | |
int V, E, u, v; cin >> V >> E; | |
vector<int> G[V]; | |
for(int i = 0; i < E; ++i) { | |
cin >> u >> v; | |
addEdge(G, u-1, v-1); | |
} | |
cout << DFSDisconnected(G, V) << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment