Welcome to Day 30 of my 100 Days of DSA challenge! Today, I delved into advanced graph techniques and the Union-Find algorithm, a powerful tool for managing disjoint sets and solving connectivity problems. From detecting cycles in graphs to merging accounts efficiently, these tasks demonstrated the versatility of Union-Find in tackling complex graph scenarios.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s explore the challenges solved today! 🚀
1. Union-Find Algorithm
This program implements the Union-Find algorithm with path compression. Each element is initialized as its own parent. The find function uses path compression to directly link elements to their set leader, reducing tree depth. The union_sets function unites two sets by attaching the smaller tree to the larger one, using ranks to maintain balanced trees. This ensures efficient operations for checking connectivity and merging sets.
Code:
#include <iostream>
using namespace std;
#define MAX 1000 // Maximum number of elements in the Union-Find structure
class UnionFind {
private:
int parent[MAX]; // Parent array to store the leader of each set
int rank[MAX]; // Rank array to store the depth of trees
public:
UnionFind(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i; // Initialize each element as its own parent
rank[i] = 0; // Initialize rank as 0
}
}
// Find the leader (root) of a set with path compression
int find(int element) {
if (parent[element] != element) {
parent[element] = find(parent[element]); // Path compression
}
return parent[element];
}
// Union of two sets by rank
void union_sets(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if (root_x != root_y) {
// Attach smaller rank tree under the root of the higher 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 {
parent[root_y] = root_x;
rank[root_x]++;
}
}
}
// Check if two elements belong to the same set
bool are_connected(int x, int y) {
return find(x) == find(y);
}
};
int main() {
int n = 10; // Number of elements
UnionFind uf(n);
uf.union_sets(1, 2);
uf.union_sets(2, 3);
uf.union_sets(4, 5);
cout << "Are 1 and 3 connected? " << (uf.are_connected(1, 3) ? "Yes" : "No") << endl;
cout << "Are 3 and 4 connected? " << (uf.are_connected(3, 4) ? "Yes" : "No") << endl;
uf.union_sets(3, 4);
cout << "After union of 3 and 4, are 3 and 4 connected? " << (uf.are_connected(3, 4) ? "Yes" : "No") << endl;
return 0;
}
Output:
2. Detect a Cycle in an Undirected Graph
This program uses the Union-Find algorithm to detect cycles in an undirected graph. Each node starts as its own parent. The find function ensures efficient root tracking with path compression. The union_sets function merges two sets by rank and checks if the nodes are already connected. If they are, a cycle is detected. The program reads the graph edges, applies union_sets, and detects a cycle if any edge connects nodes already in the same set.
Code:
#include <iostream>
using namespace std;
#define MAX 1000
class UnionFind {
private:
int parent[MAX]; // Parent array to track roots of elements
int rank[MAX]; // Rank array to optimize union operation
public:
// Initialize the Union-Find structure
UnionFind(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i; // Each node is its own parent initially
rank[i] = 0; // All ranks start as 0
}
}
// Find the root of a set, with path compression
int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]); // Path compression
}
return parent[node];
}
// Union by rank to merge two sets
bool union_sets(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u == root_v) {
return true; // Cycle detected
}
// Union by rank
if (rank[root_u] > rank[root_v]) {
parent[root_v] = root_u;
} else if (rank[root_u] < rank[root_v]) {
parent[root_u] = root_v;
} else {
parent[root_v] = root_u;
rank[root_u]++;
}
return false;
}
};
int main() {
int num_nodes, num_edges;
cout << "Enter the number of nodes and edges: ";
cin >> num_nodes >> num_edges;
UnionFind uf(num_nodes);
cout << "Enter the edges (u v):" << endl;
for (int i = 0; i < num_edges; i++) {
int u, v;
cin >> u >> v;
if (uf.union_sets(u, v)) {
cout << "Cycle detected in the graph." << endl;
return 0;
}
}
cout << "No cycle detected in the graph." << endl;
return 0;
}
Output:
3. Smallest String with Swaps
This program solves the "smallest string with swaps" problem using the Union-Find data structure. It identifies connected components of indices based on the given pairs, groups characters in those components, and replaces characters with the lexicographically smallest order within each component. The result is built by reconstructing the string with sorted characters from each group.
Code:
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define MAX 1000
class UnionFind {
private:
int parent[MAX];
int rank[MAX];
public:
UnionFind(int size) {
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]); // Path compression
}
return parent[node];
}
void union_sets(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u != root_v) {
if (rank[root_u] > rank[root_v]) {
parent[root_v] = root_u;
} else if (rank[root_u] < rank[root_v]) {
parent[root_u] = root_v;
} else {
parent[root_v] = root_u;
rank[root_u]++;
}
}
}
};
string smallest_string_with_swaps(string s, pair<int, int> pairs[], int pair_count) {
int n = s.size();
UnionFind uf(n);
// Build the Union-Find structure from the pairs
for (int i = 0; i < pair_count; i++) {
uf.union_sets(pairs[i].first, pairs[i].second);
}
// Group indices by their connected components
map<int, multiset<char>> component_chars;
for (int i = 0; i < n; i++) {
int root = uf.find(i);
component_chars[root].insert(s[i]);
}
// Construct the smallest string
string result = s;
for (int i = 0; i < n; i++) {
int root = uf.find(i);
result[i] = *component_chars[root].begin();
component_chars[root].erase(component_chars[root].begin());
}
return result;
}
int main() {
string s = "dcab";
pair<int, int> pairs[] = {{0, 3}, {1, 2}, {0, 2}};
int pair_count = sizeof(pairs) / sizeof(pairs[0]);
cout << "Smallest String: " << smallest_string_with_swaps(s, pairs, pair_count) << endl;
return 0;
}
Output:
4. Connected Components in an Undirected Graph
This program finds the number of connected components in an undirected graph using the Union-Find data structure. It initializes each node as its own parent and uses path compression to optimize the find operation. The union_sets function merges two sets by rank. To determine connected components, it counts how many nodes are their own parents after performing all unions.
Code:
// Solve the "connected components in an undirected graph" problem using Union-Find.
#include <iostream>
using namespace std;
#define MAX 1000
class UnionFind {
private:
int parent[MAX]; // Array to store parent of each node
int rank[MAX]; // Array to store rank of each node
public:
// Constructor to initialize the parent and rank arrays
UnionFind(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i; // Each node is its own parent initially
rank[i] = 0; // Rank is initialized to 0
}
}
// Function to find the representative of a set
int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]); // Path compression
}
return parent[node];
}
// Function to union two sets
void union_sets(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u != root_v) {
if (rank[root_u] > rank[root_v]) {
parent[root_v] = root_u; // Attach smaller rank tree under root of higher rank tree
} else if (rank[root_u] < rank[root_v]) {
parent[root_u] = root_v;
} else {
parent[root_v] = root_u;
rank[root_u]++;
}
}
}
// Function to count connected components
int count_connected_components(int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i) { // Nodes that are their own parent are representatives
count++;
}
}
return count;
}
};
int main() {
int n, edges;
cout << "Enter the number of nodes: ";
cin >> n;
cout << "Enter the number of edges: ";
cin >> edges;
UnionFind uf(n);
cout << "Enter the edges (u v):" << endl;
for (int i = 0; i < edges; i++) {
int u, v;
cin >> u >> v;
uf.union_sets(u, v);
}
cout << "Number of connected components: " << uf.count_connected_components(n) << endl;
return 0;
}
Output:
5. Accounts Merge Problem
Code:
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;
class UnionFind {
private:
int parent[1000];
int rank[1000];
public:
// Constructor initializes each node as its own parent
UnionFind(int size) {
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// Find the root of the set containing 'x'
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
// Union two sets by rank
void union_sets(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if (root_x != root_y) {
if (rank[root_x] > rank[root_y]) {
parent[root_y] = root_x;
} else if (rank[root_x] < rank[root_y]) {
parent[root_x] = root_y;
} else {
parent[root_y] = root_x;
rank[root_x]++;
}
}
}
};
void accounts_merge(string accounts[][2], int n) {
unordered_map<string, int> email_to_id; // Map email to unique ID
map<int, set<string>> id_to_emails; // Map ID to unique emails
UnionFind uf(n);
// Associate each email with an account ID
for (int i = 0; i < n; i++) {
for (int j = 1; accounts[i][j] != ""; j++) {
string email = accounts[i][j];
if (email_to_id.find(email) == email_to_id.end()) {
email_to_id[email] = i;
} else {
uf.union_sets(i, email_to_id[email]);
}
}
}
// Group emails by root ID
for (auto &entry : email_to_id) {
string email = entry.first;
int id = uf.find(entry.second);
id_to_emails[id].insert(email);
}
// Print merged accounts
for (auto &entry : id_to_emails) {
int id = entry.first;
cout << accounts[id][0]; // Account name
for (const string &email : entry.second) {
cout << " " << email;
}
cout << endl;
}
}
int main() {
string accounts[4][2] = {
{"John", "johnsmith@mail.com"},
{"John", "john00@mail.com"},
{"Mary", "mary@mail.com"},
{"John", "johnnybravo@mail.com"}
};
accounts_merge(accounts, 4);
return 0;
}
Output:
Day 30 showcased the power of the Union-Find algorithm in solving complex graph problems efficiently. From cycle detection to merging data structures, these challenges highlighted the importance of mastering Union-Find for tackling connectivity and grouping problems in graphs. 🚀