connected components Algorithm
Connected Components with DSU Algorithm refers to the process of identifying connected components in an undirected graph using Disjoint Set Union (DSU) data structure, which is also known as Union-Find. Connected components are the subsets of vertices in a graph where each vertex is reachable from any other vertex within the same subset. The DSU data structure is used to efficiently manage the connections between the vertices and determine which vertices belong to the same connected component. This data structure supports two primary operations: find and union. The find operation determines the representative element (or the parent) of a given element in a set, while the union operation merges two sets that contain the given elements, forming a new connected component.
The Connected Components with DSU Algorithm starts by initializing each vertex as its own parent, representing a separate connected component. Then, for each edge in the graph, the algorithm performs a find operation on both vertices of the edge. If the representative elements (parents) of both vertices are different, it means they belong to distinct connected components, and a union operation is performed to merge the two components. After processing all edges, the connected components can be determined by grouping vertices with the same representative element (parent). The algorithm's efficiency comes from the fact that union and find operations can be performed in nearly constant time using path compression and union by rank optimizations. This makes the Connected Components with DSU Algorithm suitable for analyzing large graphs and solving problems that require efficient handling of connected components.
#include <iostream>
#include <vector>
using std::vector;
class graph {
private:
vector<vector<int>> adj;
int connected_components;
void depth_first_search();
void explore(int, vector<bool>&);
public:
explicit graph(int n): adj(n, vector<int>()) {
connected_components = 0;
}
void addEdge(int, int);
int getConnectedComponents() {
depth_first_search();
return connected_components;
}
};
void graph::addEdge(int u, int v) {
adj[u-1].push_back(v-1);
adj[v-1].push_back(u-1);
}
void graph::depth_first_search() {
int n = adj.size();
vector<bool> visited(n, false);
for (int i = 0 ; i < n ; i++) {
if (!visited[i]) {
explore(i, visited);
connected_components++;
}
}
}
void graph::explore(int u, vector<bool> &visited) {
visited[u] = true;
for (auto v : adj[u]) {
if (!visited[v]) {
explore(v, visited);
}
}
}
int main() {
graph g(4);
g.addEdge(1, 2);
g.addEdge(3, 2);
std::cout << g.getConnectedComponents();
return 0;
}
