#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// 并查集用于Kruskal算法
class UnionFind {
private:
    vector<int> parent, rank;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        // 按秩合并
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        
        return true;
    }
};

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

class KruskalMST {
private:
    vector<Edge> edges;
    int n;
    
public:
    KruskalMST(int vertices) : n(vertices) {}
    
    void addEdge(int u, int v, int w) {
        edges.push_back({u, v, w});
    }
    
    pair<int, vector<Edge>> findMST() {
        sort(edges.begin(), edges.end()); // 按权重排序
        UnionFind uf(n);
        
        vector<Edge> mst;
        int totalWeight = 0;
        
        for (const Edge& e : edges) {
            if (uf.unite(e.u, e.v)) { // 不形成环
                mst.push_back(e);
                totalWeight += e.weight;
                if (mst.size() == n - 1) break;
            }
        }
        
        return {totalWeight, mst};
    }
};

int main() {
    cout << "Kruskal最小生成树算法测试:" << endl;
    
    KruskalMST kruskal(4);
    kruskal.addEdge(0, 1, 10);
    kruskal.addEdge(0, 2, 6);
    kruskal.addEdge(0, 3, 5);
    kruskal.addEdge(1, 3, 15);
    kruskal.addEdge(2, 3, 4);
    
    auto [weight, mst] = kruskal.findMST();
    
    cout << "MST总权重: " << weight << endl;
    cout << "MST边:" << endl;
    for (const Edge& e : mst) {
        cout << e.u << " - " << e.v << " (权重: " << e.weight << ")" << endl;
    }
    
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class DijkstraWithPath {
private:
    vector<vector<pair<int, int>>> graph;
    int n;
    
public:
    DijkstraWithPath(int vertices) : n(vertices), graph(vertices) {}
    
    void addEdge(int u, int v, int w) {
        graph[u].push_back({v, w});
    }
    
    pair<vector<int>, vector<int>> shortestPath(int start) {
        vector<int> dist(n, INT_MAX);
        vector<int> parent(n, -1);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        dist[start] = 0;
        pq.push({0, start});
        
        while (!pq.empty()) {
            int d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto& edge : graph[u]) {
                int v = edge.first;
                int w = edge.second;
                
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return {dist, parent};
    }
    
    vector<int> reconstructPath(const vector<int>& parent, int start, int end) {
        vector<int> path;
        int curr = end;
        
        while (curr != -1) {
            path.push_back(curr);
            curr = parent[curr];
        }
        
        reverse(path.begin(), path.end());
        
        // 检查路径是否存在
        if (path[0] != start) {
            return {};
        }
        
        return path;
    }
};

int main() {
    cout << "带路径重构的Dijkstra算法测试:" << endl;
    
    DijkstraWithPath dijkstra(5);
    dijkstra.addEdge(0, 1, 4);
    dijkstra.addEdge(0, 2, 2);
    dijkstra.addEdge(1, 2, 1);
    dijkstra.addEdge(1, 3, 5);
    dijkstra.addEdge(2, 3, 8);
    dijkstra.addEdge(2, 4, 10);
    dijkstra.addEdge(3, 4, 2);
    
    auto [dist, parent] = dijkstra.shortestPath(0);
    
    cout << "从顶点0的最短距离:" << endl;
    for (int i = 0; i < dist.size(); i++) {
        cout << "到 " << i << ": " << dist[i] << endl;
    }
    
    cout << "\n从0到4的路径:" << endl;
    vector<int> path = dijkstra.reconstructPath(parent, 0, 4);
    for (int i = 0; i < path.size(); i++) {
        cout << path[i];
        if (i < path.size() - 1) cout << " -> ";
    }
    cout << endl;
    
    return 0;
}