Graph Valid Tree

class DisjointSet {

    private int[] leader;
    private int[] rank;

    public DisjointSet(int size) {
        leader = new int[size];
        rank = new int[size];
        for (int index = 0; index < size; index++) {
            leader[index] = index;
            rank[index] = 1;
        }
    }

    public int find(int x) {
        int root = x;
        while (leader[root] != root) {
            root = leader[root];
        }
        while (x != root) {
            int next = leader[x];
            leader[x] = root;
            x = next;
        }
        return root;
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        if (rank[rootX] < rank[rootY]) {
            leader[rootX] = rootY;
            rank[rootY] += rank[rootX];
        } else {
            leader[rootY] = rootX;
            rank[rootX] += rank[rootY];
        }
        return true;
    }
}

class GraphValidation {

    public boolean isValidTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        DisjointSet ds = new DisjointSet(n);
        for (int[] edge : edges) {
            if (!ds.union(edge[0], edge[1])) {
                return false;
            }
        }
        return true;
    }

}

The provided Java code defines two classes, DisjointSet and GraphValidation, to determine if a given graph represents a valid tree. Here's a breakdown of the solution approach:

• DisjointSet Class:

  • Implements a Union-Find data structure using path compression and union by rank to help in efficiently managing and merging sets.
  • Constructor (DisjointSet): Initializes the leader and rank arrays. Each node is its own leader initially, and all ranks are set to 1.
  • find method: Retrieves the root leader of a node, performing path compression along the way to flatten the structure, improving future search operations.
  • union method: Merges two sets identified by nodes x and y. Uses the root of these nodes and merges smaller ranked trees under larger ranked ones to maintain balance. Returns false if the nodes are already connected, indicating a cycle.

• GraphValidation Class:

  • Contains the isValidTree method to check if the input graph represented as n nodes and a list of edges defines a valid tree.
  • isValidTree Method:
    • Checks if the number of edges is exactly one less than the number of nodes, a necessary condition for a valid tree.
    • Utilizes the DisjointSet to process each edge, trying to union the nodes of the edge.
    • If a union operation returns false at any point, it signifies the presence of a cycle, making the structure not a valid tree.
    • If all edges process without detecting a cycle, and the number of edges is correct, the structure is considered a valid tree.

In essence, this code effectively checks for the key properties of a tree in a graph, such as connectivity and the absence of cycles, using a Union-Find structure with optimizations for efficient set operations.

class DisjointSetUnion:

    def __init__(self, size):
        self.leader = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, x):
        if self.leader[x] != x:
            self.leader[x] = self.find(self.leader[x])
        return self.leader[x]

    def merge(self, x, y):
        lead_x = self.find(x)
        lead_y = self.find(y)
        if lead_x == lead_y:
            return False
        if self.rank[lead_x] < self.rank[lead_y]:
            self.leader[lead_x] = lead_y
            self.rank[lead_y] += self.rank[lead_x]
        else:
            self.leader[lead_y] = lead_x
            self.rank[lead_x] += self.rank[lead_y]
        return True

class Solution:
    def isValidGraph(self, node_count: int, connections: List[List[int]]) -> bool:
        if len(connections) != node_count - 1:
            return False

        dsu = DisjointSetUnion(node_count)

        for node1, node2 in connections:
            if not dsu.merge(node1, node2):
                return False

        return True

The Python3 solution provided uses the Disjoint Set Union (DSU) data structure to determine if a given graph forms a valid tree. The graph's validity as a tree is confirmed through two conditions:

• The graph must exactly have node_count - 1 connections to form a valid tree without any cycles.
• All nodes must be connected in a single component.

Key steps and features of the implementation are as follows:

• Initialization of DSU: A class DisjointSetUnion is initialized with each node being its own leader and having an initial rank of 1. These ranks help in optimizing the union operations by always attaching the smaller tree under the larger tree, thus keeping the depth of the tree minimal.
• Functions in DSU:
  • find: This method uses path compression. When finding the leader of a node, it sets the leader of each traversed node directly to the root leader. This optimizes future operations involving these nodes.
  • merge: It connects two nodes. If they share the same leader, a cycle is detected, and it returns False. Otherwise, it merges the sets by size and updates ranks accordingly, returning True to indicate a successful merge without a cycle.
• Graph Validity Check: The isValidGraph method first checks the number of connections. It then iterates through each connection, attempting to merge the components of the two nodes involved. If any merge attempt returns False, it indicates a cycle, and the function returns False. If all merges are successful, and the total connections match node_count - 1, it confirms that the graph is a valid tree.

This structured and efficient approach using DSU ensures the solution handles both connectivity and cycle detection effectively, making it a robust solution for checking if a graph is a valid tree.