Kruskal算法用链表判断回路C++实现

以下是Kruskal算法用链表判断回路的C++实现：

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int u, v, w;
};

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
    ~ListNode() { delete next; }
};

int find(int x, vector<int>& parent) {
    if (parent[x] != x) {
        parent[x] = find(parent[x], parent);
    }
    return parent[x];
}

bool merge(int x, int y, vector<int>& parent) {
    int px = find(x, parent);
    int py = find(y, parent);
    if (px == py) {
        return false;
    }
    parent[px] = py;
    return true;
}

bool hasCycle(vector<ListNode*>& edges, int n) {
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    for (auto& head : edges) {
        while (head->next) {
            int u = head->val;
            int v = head->next->val;
            if (!merge(u, v, parent)) {
                return true;
            }
            head = head->next;
        }
    }
    return false;
}

vector<Edge> kruskal(vector<Edge>& edges, int n) {
    vector<ListNode*> adj(n);
    for (int i = 0; i < n; i++) {
        adj[i] = new ListNode(i);
    }
    for (auto& e : edges) {
        adj[e.u]->next = new ListNode(e.v);
        adj[e.v]->next = new ListNode(e.u);
    }
    vector<Edge> result;
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.w < b.w;
    });
    for (auto& e : edges) {
        if (!merge(e.u, e.v, adj)) {
            continue;
        }
        result.push_back(e);
        if (result.size() == n - 1) {
            break;
        }
    }
    if (result.size() != n - 1 || hasCycle(adj, n)) {
        result.clear();
    }
    for (auto& head : adj) {
        delete head;
    }
    return result;
}

int main() {
    int n = 5;
    vector<Edge> edges{{0, 1, 2}, {0, 3, 6}, {1, 3, 3}, {1, 2, 5}, {1, 4, 1}, {2, 4, 4}, {3, 4, 7}};
    auto result = kruskal(edges, n);
    if (result.empty()) {
        cout << "No MST found!" << endl;
    } else {
        cout << "MST found:" << endl;
        int sum = 0;
        for (auto& e : result) {
            cout << e.u << " " << e.v << " " << e.w << endl;
            sum += e.w;
        }
        cout << "Total weight: " << sum << endl;
    }
    return 0;
}

此处实现了两个函数：

- `merge(int x, int y, vector<int>& parent)`：将编号为x和y的两个点所在的连通块合并。如果它们原本就在同一个连通块中，返回false；否则返回true。
- `hasCycle(vector<ListNode*>& edges, int n)`：用并查集判断图中是否存在环。如果存在，返回true；否则返回false。

注意到使用链表存储边时，遍历链表的过程可以写成一个while循环。