owlingcode

Spanning Tree Fundamentals

A spanning tree of a connected graph is a subgraph that connects all vertices with exactly n-1 edges, forming a tree. The Minimum Spanning Tree (MST) is the spanning tree with minimum total edge weight.

Edge Structure

struct Edge {
    int u, v, weight;
    
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
    
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};
                    

Union-Find Data Structure

Union-Find (Disjoint Set Union) is crucial for Kruskal's algorithm to efficiently detect cycles:

class UnionFind {
private:
    vector<int> parent, rank;
    int components;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }
    
    int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if(px == py) return false; // Already in same component
        
        // Union by rank
        if(rank[px] < rank[py]) {
            parent[px] = py;
        } else if(rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        
        components--;
        return true;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    int getComponents() {
        return components;
    }
    
    vector<vector<int>> getComponentGroups() {
        map<int, vector<int>> groups;
        for(int i = 0; i < parent.size(); i++) {
            groups[find(i)].push_back(i);
        }
        
        vector<vector<int>> result;
        for(auto& [root, group] : groups) {
            result.push_back(group);
        }
        return result;
    }
};
                    

Kruskal's Algorithm

Kruskal's algorithm builds MST by adding edges in order of increasing weight, skipping edges that would create cycles:

// Kruskal's algorithm for MST
pair<long long, vector<Edge>> kruskalMST(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end()); // Sort by weight
    
    UnionFind uf(n);
    vector<Edge> mstEdges;
    long long totalWeight = 0;
    
    for(Edge& edge : edges) {
        if(uf.unite(edge.u, edge.v)) {
            mstEdges.push_back(edge);
            totalWeight += edge.weight;
            
            // MST complete when we have n-1 edges
            if(mstEdges.size() == n - 1) break;
        }
    }
    
    // Check if MST exists (graph is connected)
    if(mstEdges.size() != n - 1) {
        return {-1, {}}; // Graph is not connected
    }
    
    return {totalWeight, mstEdges};
}

// Kruskal with custom comparator
struct EdgeComparator {
    bool operator()(const Edge& a, const Edge& b) const {
        if(a.weight != b.weight) return a.weight < b.weight;
        if(a.u != b.u) return a.u < b.u;
        return a.v < b.v;
    }
};

long long kruskalCustom(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), EdgeComparator());
    
    UnionFind uf(n);
    long long totalWeight = 0;
    int edgesUsed = 0;
    
    for(Edge& edge : edges) {
        if(!uf.connected(edge.u, edge.v)) {
            uf.unite(edge.u, edge.v);
            totalWeight += edge.weight;
            edgesUsed++;
            
            if(edgesUsed == n - 1) break;
        }
    }
    
    return (edgesUsed == n - 1) ? totalWeight : -1;
}
                    

Prim's Algorithm

Prim's algorithm grows the MST by always adding the minimum weight edge connecting the current tree to a new vertex:

// Prim's algorithm using priority queue
long long primMST(int n, vector<vector<pair<int, int>>>& adj) {
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater> pq;
    
    minEdge[0] = 0;
    pq.push({0, 0}); // {weight, vertex}
    
    long long totalWeight = 0;
    
    while(!pq.empty()) {
        int weight = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if(inMST[u]) continue;
        
        inMST[u] = true;
        totalWeight += weight;
        
        // Update adjacent vertices
        for(auto& edge : adj[u]) {
            int v = edge.first;
            int edgeWeight = edge.second;
            
            if(!inMST[v] && edgeWeight < minEdge[v]) {
                minEdge[v] = edgeWeight;
                pq.push({edgeWeight, v});
            }
        }
    }
    
    // Check if all vertices are included
    for(int i = 0; i < n; i++) {
        if(!inMST[i]) return -1; // Graph not connected
    }
    
    return totalWeight;
}

// Prim's with edge tracking
pair<long long, vector<pair<int, int>>> primMSTWithEdges(int n, vector<vector<pair<int, int>>>& adj) {
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INT_MAX);
    vector<int> parent(n, -1);
    
    minEdge[0] = 0;
    long long totalWeight = 0;
    vector<pair<int, int>> mstEdges;
    
    for(int i = 0; i < n; i++) {
        int u = -1;
        
        // Find minimum edge to add to MST
        for(int v = 0; v < n; v++) {
            if(!inMST[v] && (u == -1 || minEdge[v] < minEdge[u])) {
                u = v;
            }
        }
        
        if(minEdge[u] == INT_MAX) {
            return {-1, {}}; // Graph not connected
        }
        
        inMST[u] = true;
        totalWeight += minEdge[u];
        
        if(parent[u] != -1) {
            mstEdges.push_back({parent[u], u});
        }
        
        // Update adjacent vertices
        for(auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if(!inMST[v] && weight < minEdge[v]) {
                minEdge[v] = weight;
                parent[v] = u;
            }
        }
    }
    
    return {totalWeight, mstEdges};
}
                    

Advanced MST Algorithms

Maximum Spanning Tree

Find spanning tree with maximum total weight:

// Maximum spanning tree (reverse edge weights)
long long maximumSpanningTree(int n, vector<Edge>& edges) {
    // Negate weights for maximum spanning tree
    for(Edge& edge : edges) {
        edge.weight = -edge.weight;
    }
    
    long long maxWeight = kruskalMST(n, edges).first;
    
    // Restore original weights
    for(Edge& edge : edges) {
        edge.weight = -edge.weight;
    }
    
    return (maxWeight == -1) ? -1 : -maxWeight;
}
                    

MST with Fixed Edges

// MST including certain required edges
long long mstWithRequiredEdges(int n, vector<Edge>& allEdges, vector<Edge>& requiredEdges) {
    UnionFind uf(n);
    long long totalWeight = 0;
    int edgesUsed = 0;
    
    // First, add all required edges
    for(Edge& edge : requiredEdges) {
        if(!uf.connected(edge.u, edge.v)) {
            uf.unite(edge.u, edge.v);
            totalWeight += edge.weight;
            edgesUsed++;
        } else {
            // Required edge creates cycle - impossible
            return -1;
        }
    }
    
    // Sort remaining edges
    vector<Edge> remainingEdges;
    for(Edge& edge : allEdges) {
        bool isRequired = false;
        for(Edge& req : requiredEdges) {
            if((edge.u == req.u && edge.v == req.v) || 
               (edge.u == req.v && edge.v == req.u)) {
                isRequired = true;
                break;
            }
        }
        if(!isRequired) {
            remainingEdges.push_back(edge);
        }
    }
    
    sort(remainingEdges.begin(), remainingEdges.end());
    
    // Add remaining edges using Kruskal's
    for(Edge& edge : remainingEdges) {
        if(uf.unite(edge.u, edge.v)) {
            totalWeight += edge.weight;
            edgesUsed++;
            
            if(edgesUsed == n - 1) break;
        }
    }
    
    return (edgesUsed == n - 1) ? totalWeight : -1;
}
                    

Second Minimum Spanning Tree

// Find second minimum spanning tree
long long secondMST(int n, vector<Edge>& edges) {
    auto [mstWeight, mstEdges] = kruskalMST(n, edges);
    if(mstWeight == -1) return -1;
    
    long long secondMstWeight = LLONG_MAX;
    
    // Try removing each MST edge and replacing with next best
    for(int skipIdx = 0; skipIdx < mstEdges.size(); skipIdx++) {
        vector<Edge> modifiedEdges;
        
        // Add all edges except the skipped MST edge
        for(int i = 0; i < edges.size(); i++) {
            bool skip = false;
            for(int j = 0; j < mstEdges.size(); j++) {
                if(j == skipIdx) continue;
                
                if((edges[i].u == mstEdges[j].u && edges[i].v == mstEdges[j].v) ||
                   (edges[i].u == mstEdges[j].v && edges[i].v == mstEdges[j].u)) {
                    skip = true;
                    break;
                }
            }
            
            if(!skip && 
               !((edges[i].u == mstEdges[skipIdx].u && edges[i].v == mstEdges[skipIdx].v) ||
                 (edges[i].u == mstEdges[skipIdx].v && edges[i].v == mstEdges[skipIdx].u))) {
                modifiedEdges.push_back(edges[i]);
            }
        }
        
        auto [weight, _] = kruskalMST(n, modifiedEdges);
        if(weight != -1 && weight > mstWeight) {
            secondMstWeight = min(secondMstWeight, weight);
        }
    }
    
    return (secondMstWeight == LLONG_MAX) ? -1 : secondMstWeight;
}