Graph Connectivity Using Union-Find

The problem involves determining whether a path exists between two nodes in an undirected graph represented by edge pairs. While traditional graph search algorithms like BFS or DFS could solve this, the Union-Find data structure provides a more efficient approach with beter space complexity.

Union-Find Fundamentals

Union-Find maintains connectivity enformation using a one-dimensional array where each index represents a node, and the stored value indicates its parent node. By tracing parent relationships, we can determine if two nodes belong to the same connected component.

Implementation Template

First, we define our data structure with appropriate size:

class GraphConnectivity {
    int MAX_NODES = 200005;
    vector<int> parent = vector<int>(MAX_NODES, 0);
};

Initialization

Initially, each node is its own parent:

void initialize() {
    for (int i = 0; i < MAX_NODES; ++i) {
        parent[i] = i;
    }
}

Finding Root with Path Compression

The optimized find operation with path compression:

int findRoot(int node) {
    if (node == parent[node]) return node;
    return parent[node] = findRoot(parent[node]);
}

Union Operation

Connecting two nodes by merging their sets:

void connectNodes(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    if (x == y) return;
    parent[y] = x;
}

Connectivity Check

Determining if two nodes are connected:

bool checkConnection(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    return x == y;
}

Complete Solution

Here's the complete implementation for solving graph connectivity problems:

class GraphConnectivity {
public:
    int MAX_NODES = 200005;
    vector<int> parent = vector<int>(MAX_NODES, 0);
    
    void initialize() {
        for (int i = 0; i < MAX_NODES; ++i) {
            parent[i] = i;
        }
    }
    
    int findRoot(int node) {
        if (node == parent[node]) return node;
        return parent[node] = findRoot(parent[node]);
    }
    
    void connectNodes(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (x == y) return;
        parent[y] = x;
    }
    
    bool checkConnection(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        return x == y;
    }
    
    bool hasValidPath(int nodeCount, vector<vector<int>>& edges, int start, int end) {
        initialize();
        for (auto& edge : edges) {
            connectNodes(edge[0], edge[1]);
        }
        return checkConnection(start, end);
    }
};

The algorithm processes all edges to build connectivity relationships, then simply checks if the start and end nodes share the same root.