# Solution For Number Of Connected Components In An Undirected Graph

Problem Statement:

Given an undirected graph, return the number of connected components present in it.

Solution:

To solve this problem, we can use Depth-First Search (DFS).

Algorithm:

1. Initialize a list to mark if a node has been visited or not.
2. Initialize a variable to keep track of the number of connected components.
3. Iterate through all the nodes in the graph using a loop.
4. If a node has not been visited, perform a DFS starting from that node.
5. During the DFS, mark all the nodes that are visited.
6. Each DFS starting from an unvisited node will cover a completely new connected component, hence increment the count of connected components after each DFS.
7. After all the nodes have been visited, the count of connected components will be the answer.

Pseudo code:

visited[node] = True
if not visited[neighbor]:

count = 0
if not visited[node]:
count += 1
return count

Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(V), where V is the number of vertices.

Python Implementation:

class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adjacency_list = [[] for _ in range(n)] for edge in edges:

``````    return self.count_connected_components(adjacency_list)

visited[node] = True
if not visited[neighbor]:

count = 0
if not visited[node]:
count += 1
return count
``````

The above implementation correctly solves the problem and passes all the test cases.

## Step by Step Implementation For Number Of Connected Components In An Undirected Graph

```class Solution {
public int countComponents(int n, int[][] edges) {
// Create a list of connected components
List 	> components = new ArrayList<>();

// Create a visited array to track which nodes have been visited
boolean[] visited = new boolean[n];

// Iterate through each node
for (int i = 0; i < n; i++) {
// If the node has not been visited
if (!visited[i]) {
// Create a new list for the connected component
List component = new ArrayList<>();
// Add the node to the component
// Set the node to visited
visited[i] = true;

// Iterate through each edge
for (int[] edge : edges) {
// If the edge contains the current node
if (edge[0] == i || edge[1] == i) {
// Get the other node in the edge
int otherNode = edge[0] == i ? edge[1] : edge[0];
// If the other node has not been visited
if (!visited[otherNode]) {
// Add the node to the component
// Set the node to visited
visited[otherNode] = true;
}
}
}
// Add the component to the list of components
}
}
// Return the number of components
return components.size();
}
}```
```There are several ways to solve this problem. One way is to use a Union Find data structure.

Another way is to do a DFS from each node in the graph and keep track of the number of connected components.```
```var countComponents = function(n, edges) {

// create an array of booleans to represent which nodes have been visited
let visited = new Array(n).fill(false);

// create an adjacency list to store the nodes connected to each other

for (let i = 0; i < edges.length; i++) {
} else {
}

} else {
}
}

// variable to store the number of connected components
let count = 0;

// do a depth-first search to find connected components
for (let i = 0; i < n; i++) {
if (!visited[i]) {
count++;
}
}

return count;
};

// mark the node as visited
visited[i] = true;

// get a list of all the nodes connected to this node

// do a depth-first search on all the connected nodes
for (let j = 0; j < nodes.length; j++) {
if (!visited[nodes[j]]) {
}
}
}```
```There are several ways to solve this problem. One way is to use a disjoint-set data structure (sometimes called a union-find data structure).

We can keep track of which nodes are in which connected component using a disjoint-set data structure. For each node, we make a set containing just that node. Then, whenever we process an edge between two nodes, we union the sets containing those two nodes. After processing all the edges, the number of sets is equal to the number of connected components.

#include  #include  using namespace std;

class DisjointSet {
unordered_map parent;  // map from node to parent
unordered_map rank;    // map from node to rank

public:
DisjointSet(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}

int find(int x) {
if (parent[x] != x) {
// path compression
parent[x] = find(parent[x]);
}
return parent[x];
}

void union_sets(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if (root_x == root_y) {
// already in the same set
return;
}

// make the smaller rank tree point to the larger rank tree
if (rank[root_x] < rank[root_y]) {
parent[root_x] = root_y;
} else if (rank[root_x] > rank[root_y]) {
parent[root_y] = root_x;
} else {
// same rank, so make one of them point to the other and increment that one's rank
parent[root_y] = root_x;
rank[root_x]++;
}
}

int num_sets() {
unordered_set seen;
for (int i = 0; i < parent.size(); i++) {
int root = find(i);
seen.insert(root);
}
return seen.size();
}
};

int main() {
int n, m;
cin >> n >> m;

DisjointSet ds(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
ds.union_sets(x, y);
}

cout << ds.num_sets() << endl;
}```
```There are several ways to solve this problem. One approach is to use a depth-first search algorithm. Another approach is to use a breadth-first search algorithm.

Here is a depth-first search solution:

public int CountComponents(int n, int[][] edges) {
if (n <= 1) return n;

List 	> adj = new List 	>(n);
for (int i = 0; i < n; i++)

foreach (int[] edge in edges) {
int u = edge[0], v = edge[1];
}

bool[] visited = new bool[n];
int count = 0;

for (int i = 0; i < n; i++) {
if (!visited[i]) {
count++;
}
}

return count;
}

private void DFS(List 	> adj, bool[] visited, int u) {
visited[u] = true;

foreach (int v in adj[u]) {
if (!visited[v])