Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree - Problem

Union Find Graph Sorting Minimum Spanning Tree Strongly Connected Component Hard

Network Infrastructure Analysis: You're designing a critical network infrastructure connecting n cities. Given a weighted undirected graph where edges[i] = [ai, bi, weighti] represents a connection between cities ai and bi with cost weighti.

Your task is to analyze the Minimum Spanning Tree (MST) - the most cost-effective way to connect all cities. You need to classify edges into two categories:

🔴 Critical Edges: Removing these edges would increase the total MST cost (network becomes more expensive)
🟡 Pseudo-Critical Edges: These edges can appear in some MSTs but aren't essential (alternative equally good solutions exist)

Goal: Return two lists containing the indices of critical and pseudo-critical edges respectively.

Input & Output

example_1.py — Basic Network

$ Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,3,4],[2,3,1],[1,3,2]]

› Output: [[0,5],[1,2,3,4,6]]

💡 Note: Edge 0 connects nodes 0-1 with weight 1, and edge 5 connects nodes 2-3 with weight 1. These are critical because removing either would force using heavier alternatives. The remaining edges can appear in some MSTs but aren't essential.

example_2.py — Triangle Graph

$ Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,1],[0,4,1]]

› Output: [[],[0,1,2,3,4]]

💡 Note: This forms a cycle where any 4 edges can create a valid MST with weight 4. No edges are critical, but all are pseudo-critical since each can be part of an optimal solution.

example_3.py — Bridge Network

$ Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1]]

› Output: [[0,1,2],[]]

💡 Note: This is a path graph where every edge is essential for connectivity. All edges are critical, and none are merely pseudo-critical.

Constraints

2 ≤ n ≤ 100
1 ≤ edges.length ≤ min(200, n × (n-1) / 2)
edges[i].length == 3
0 ≤ a_i < b_i < n
1 ≤ weight_i ≤ 1000
All edge weights are distinct (no duplicate weights)
There is no repeated edge in the graph

Visualization

Tap to expand

Understanding the Visualization

🗺️ Survey the Territory

Identify all possible road connections between cities with their construction costs

📊 Find Optimal Network

Use Kruskal's algorithm to determine the minimum cost to connect all cities

🔍 Test Road Importance

For each road, see what happens if we remove it - does cost increase?

🛣️ Test Alternative Routes

For non-critical roads, see if including them first still gives optimal cost

📋 Classify Infrastructure

Critical roads are mandatory, pseudo-critical roads are optional but viable

Key Takeaway

🎯 Key Insight: An edge is critical if removing it breaks the optimal cost, and pseudo-critical if it can be part of an optimal solution but isn't mandatory. Use Kruskal's algorithm with systematic edge testing to classify each connection efficiently.

Asked in

G Google 45

The optimal approach uses Kruskal's algorithm with edge testing. First, find the original MST weight. Then for each edge: test if excluding it increases the MST weight (critical), or if including it first maintains the same weight (pseudo-critical). Time complexity: O(E² log E).

Common Approaches

Approach	Time	Space	Notes
✓ Kruskal + Edge Testing (Standard Approach)	O(E² log E)	O(E + V)	Use Kruskal's algorithm to find MST, then test each edge by exclusion and forced inclusion

Kruskal + Edge Testing (Standard Approach) — Algorithm Steps

Sort all edges by weight and find the original MST weight using Kruskal's algorithm
For each edge, test if it's critical by excluding it and checking if MST weight increases
For each non-critical edge, test if it's pseudo-critical by forcing its inclusion first
If forced inclusion yields same MST weight, the edge is pseudo-critical

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Original MST

Use Kruskal's algorithm to find the minimum spanning tree weight

Test Critical Edges

For each edge, exclude it and check if MST weight increases

Test Pseudo-Critical

For non-critical edges, force inclusion and check if MST weight stays same

Classify Results

Categorize edges based on test results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
    int *parent;
    int *rank;
    int components;
} UnionFind;

UnionFind* createUF(int n) {
    UnionFind *uf = malloc(sizeof(UnionFind));
    uf->parent = malloc(n * sizeof(int));
    uf->rank = calloc(n, sizeof(int));
    uf->components = n;
    for (int i = 0; i < n; i++) uf->parent[i] = i;
    return uf;
}

int find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

int unite(UnionFind *uf, int x, int y) {
    int px = find(uf, x), py = find(uf, y);
    if (px == py) return 0;
    
    if (uf->rank[px] < uf->rank[py]) {
        uf->parent[px] = py;
    } else if (uf->rank[px] > uf->rank[py]) {
        uf->parent[py] = px;
    } else {
        uf->parent[py] = px;
        uf->rank[px]++;
    }
    uf->components--;
    return 1;
}

int compare(const void *a, const void *b) {
    int *ia = (int*)a, *ib = (int*)b;
    return ia[3] - ib[3];
}

int kruskal(int n, int edges[][4], int edgeCount, int exclude, int include) {
    UnionFind *uf = createUF(n);
    int weight = 0, edgesUsed = 0;
    
    // Include specified edge
    if (include != -1) {
        if (unite(uf, edges[include][1], edges[include][2])) {
            weight += edges[include][3];
            edgesUsed++;
        }
    }
    
    // Sort edges by weight
    qsort(edges, edgeCount, sizeof(edges[0]), compare);
    
    for (int i = 0; i < edgeCount; i++) {
        int idx = edges[i][0];
        if (idx == exclude || idx == include) continue;
        
        if (unite(uf, edges[i][1], edges[i][2])) {
            weight += edges[i][3];
            edgesUsed++;
            if (edgesUsed == n - 1) break;
        }
    }
    
    int result = (uf->components == 1) ? weight : INT_MAX;
    free(uf->parent);
    free(uf->rank);
    free(uf);
    return result;
}

int** findCriticalAndPseudoCriticalEdges(int n, int edges[][3], int edgeCount, int* returnSizes) {
    // Create indexed edges
    int indexedEdges[edgeCount][4];
    for (int i = 0; i < edgeCount; i++) {
        indexedEdges[i][0] = i;
        indexedEdges[i][1] = edges[i][0];
        indexedEdges[i][2] = edges[i][1];
        indexedEdges[i][3] = edges[i][2];
    }
    
    int originalWeight = kruskal(n, indexedEdges, edgeCount, -1, -1);
    
    int **result = malloc(2 * sizeof(int*));
    result[0] = malloc(edgeCount * sizeof(int));
    result[1] = malloc(edgeCount * sizeof(int));
    returnSizes[0] = returnSizes[1] = 0;
    
    for (int i = 0; i < edgeCount; i++) {
        // Reset edges for each test
        for (int j = 0; j < edgeCount; j++) {
            indexedEdges[j][0] = j;
            indexedEdges[j][1] = edges[j][0];
            indexedEdges[j][2] = edges[j][1];
            indexedEdges[j][3] = edges[j][2];
        }
        
        if (kruskal(n, indexedEdges, edgeCount, i, -1) > originalWeight) {
            result[0][returnSizes[0]++] = i;
        } else {
            // Reset again for include test
            for (int j = 0; j < edgeCount; j++) {
                indexedEdges[j][0] = j;
                indexedEdges[j][1] = edges[j][0];
                indexedEdges[j][2] = edges[j][1];
                indexedEdges[j][3] = edges[j][2];
            }
            if (kruskal(n, indexedEdges, edgeCount, -1, i) == originalWeight) {
                result[1][returnSizes[1]++] = i;
            }
        }
    }
    
    return result;
}

int main() {
    int edges[][3] = {{0,1,1},{1,2,1},{2,3,2},{0,3,2},{0,3,4},{2,3,1},{1,3,2}};
    int returnSizes[2];
    int **result = findCriticalAndPseudoCriticalEdges(4, edges, 7, returnSizes);
    
    printf("Critical edges: ");
    for (int i = 0; i < returnSizes[0]; i++) {
        printf("%d ", result[0][i]);
    }
    printf("\nPseudo-critical edges: ");
    for (int i = 0; i < returnSizes[1]; i++) {
        printf("%d ", result[1][i]);
    }
    printf("\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(E² log E)

For each of E edges, we run Kruskal's algorithm which takes O(E log E) time

⚡ Linearithmic

Space Complexity

O(E + V)

Space for Union-Find structure and edge sorting

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Kruskal + Edge Testing (Standard Approach) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler