✅ 100% - O(ElogE) Kruskal's Algorithm and DFS
Problem Understanding\n\nIn the problem "1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree," we are presented with a weighted undirected co
# Problem Understanding\n\nIn the problem "1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree," we are presented with a weighted undirected connected graph consisting of `n` vertices, numbered from 0 to `n - 1`. The graph is described by an array `edges`, where each element `edges[i] = [ai, bi, weighti]` represents a bidirectional edge with a weight between nodes `ai` and `bi`. The primary objective is to identify and categorize edges within the minimum spanning tree (MST) of the graph.\n\n**The Task**\n\nOur task is twofold:\n\n1. **Critical Edges**: We need to identify the critical edges within the MST. A critical edge is an edge present in the MST such that removing it from the graph would lead to an increase in the overall weight of the MST.\n\n2. **Pseudo-Critical Edges**: Additionally, we aim to pinpoint pseudo-critical edges. A pseudo-critical edge is an edge that may appear in some of the MSTs but not necessarily in all of them.\n\nIn essence, our goal is to dissect the graph\'s MST and classify edges into these two categories: critical and pseudo-critical. By addressing this problem, we gain insights into the intricacies of graph theory and optimization, as well as the significance of edge classifications within minimum spanning trees. This exercise enhances our understanding of these fundamental graph concepts and their application to real-world scenarios.\n\n---\n\n# Live Coding:\nhttps://youtu.be/wkCHl9tpoyQ\n\n# Approach: Kruskal\'s Algorithm and DFS\n\nWe\'re tasked with finding both critical and pseudo-critical edges in a Minimum Spanning Tree (MST) of a given graph. To accomplish this, we employ a blend of two well-known algorithms:\n- **Kruskal\'s Algorithm** to determine the MST.\n- **Depth-First Search (DFS)** to traverse and inspect the MST for edge classifications.\n\n## Key Components\n\n1. **Union-Find Structure**: A classic data structure to manage sets or components. It facilitates checking whether two nodes are in the same component and joining two components.\n2. **Adjacency List**: A way of representing our graph, making it easier to traverse and inspect its edges and nodes.\n\n## Approach Steps\n\n### 1. Set the Stage:\n   - Introduce the **Union-Find** data structure to help us decide if an edge can be safely added to the MST without forming a cycle.\n   - Create an **Adjacency List** to represent our graph\'s structure and relationships.\n\n### 2. Construct the MST:\n   - Begin by arranging the edges based on their weights, ensuring we always consider the smallest edge first.\n   - Proceed through these edges, and if adding an edge doesn\'t form a cycle (verified using Union-Find), incorporate it into the MST.\n\n### 3. Traverse and Classify:\n   - Use **DFS** to explore the MST. \n   - As we traverse, we record the depth or "level" of each node.\n   - Edges are then classified based on their significance to the structure and weight of the MST:\n     - **Critical Edges**: Removing them results in a more massive MST.\n     - **Pseudo-Critical Edges**: Edges that can be part of some MSTs but aren\'t mandatory for the minimum weight.\n\n### 4. Conclude:\n   - Once all edges have been inspected and classified, present them in two separate lists: one for critical edges and another for pseudo-critical ones.\n\n## Complexity Insights\n\n- **Time Complexity**: Two aspects majorly influence our solution\'s speed:\n  - **Sorting the edges**, costing $$O(E \\log E)$$ where $$E$$ is the number of edges.\n  - **Union-Find operations**, taking $$O(E \\alpha(V))$$, where $$\\alpha(V)$$ is the inverse Ackermann function. This function grows very slowly, making this part almost linear in terms of time complexity.\n  In essence, our algorithm roughly runs in $$O(E \\log E)$$.\n\n- **Space Complexity**: Our primary memory consumption sources are:\n  - Storing the graph\'s edges and nodes.\n  - The Union-Find and adjacency list structures.\n  As a result, our space needs are roughly $$O(E + V)$$, where $$E$$ is the number of edges, and $$V$$ is the number of vertices.\n\n---\n\nIn a nutshell, our approach combines classical graph algorithms and data structures to effectively classify edges in an MST, offering valuable insights into the graph\'s structure and relationships.\n\n---\n\n# Performance:\n\n| Language  | Runtime   | Runtime Beats (%) | Memory   | Memory Beats (%) |\n|-----------|-----------|-------------------|----------|------------------|\n| Python3   | 72 ms     | 100%              | 16.7 MB  | 40.66%           |\n\n\n\n---\n\n# Code\n``` Python []\n# Step 1: Union-Find Data Structure\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.rank = [0] * n\n\n    def find(self, x):\n        if self.parent[x] != x:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n\n    def union(self, x, y):\n        rootX, rootY = self.find(x), self.find(y)\n        if rootX == rootY:\n            return False\n        if self.rank[rootX] > self.rank[rootY]:\n            self.parent[rootY] = rootX\n        else:\n            self.parent[rootX] = rootY\n            if self.rank[rootX] == self.rank[rootY]:\n                self.rank[rootY] += 1\n        return True\n\n# Step 2: Main Solution\nclass Solution:\n    # Main Method\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: [[int]]) -> [[int]]:\n        \n        # Step 3: Depth-First Search (DFS) Helper Function\n        def dfs(node, depth, ancestor):\n            levels[node] = depth\n            for neighbor, edge_index in adjacency_list[node]:\n                if neighbor == ancestor:\n                    continue\n                if levels[neighbor] == -1:\n                    levels[node] = min(levels[node], dfs(neighbor, depth + 1, node))\n                else:\n                    levels[node] = min(levels[node], levels[neighbor])\n                if levels[neighbor] >= depth + 1 and edge_index not in pseudo_critical:\n                    critical.add(edge_index)\n            return levels[node]\n\n        # Step 4: Initialize Sets\n        critical, pseudo_critical = set(), set()\n\n        # Step 5: Grouping Edges By Weight\n        weight_to_edges = {w: [] for w in {edge[2] for edge in edges}}\n        for i, (u, v, w) in enumerate(edges):\n            weight_to_edges[w].append([u, v, i])\n        \n        # Step 6: Using Union-Find\n        union_find = UnionFind(n)\n        \n        # Step 7: Iterating Through Weights\n        for weight in sorted(weight_to_edges):\n            edge_lookup = defaultdict(set)\n            \n            for u, v, edge_index in weight_to_edges[weight]:\n                rootU, rootV = union_find.find(u), union_find.find(v)\n                \n                if rootU != rootV:\n                    union_pair = tuple(sorted((rootU, rootV)))\n                    edge_lookup[union_pair].add(edge_index)\n            \n            mst_edges, adjacency_list = [], defaultdict(list)\n            \n            for (rootU, rootV), edge_indexes in edge_lookup.items():\n                if len(edge_indexes) > 1:\n                    pseudo_critical.update(edge_indexes)\n                \n                edge_idx = edge_indexes.pop()\n                adjacency_list[rootU].append((rootV, edge_idx))\n                adjacency_list[rootV].append((rootU, edge_idx))\n                mst_edges.append((rootU, rootV, edge_idx))\n                union_find.union(rootU, rootV)\n            \n            levels = [-1] * n\n            \n            for u, v, _ in mst_edges:\n                if levels[u] == -1:\n                    dfs(u, 0, -1)\n            \n            for _, _, edge_index in mst_edges:\n                if edge_index not in critical:\n                    pseudo_critical.add(edge_index)\n\n        # Step 8: Return Result\n        return [list(critical), list(pseudo_critical)]\n```\n\nThis problem beautifully showcases the application of Kruskal\'s algorithm and depth-first search (DFS) to identify critical and pseudo-critical edges in a minimum spanning tree. Solving this problem provides a deep understanding of these graph algorithms and their practical use in real-world scenarios. \uD83D\uDCA1\uD83C\uDF20\uD83D\uDC69\u200D\uD83D\uDCBB\uD83D\uDC68\u200D\uD83D\uDCBB
['Union Find', 'Graph', 'Minimum Spanning Tree', 'Python3']