Kruskal算法用链表判断回路C++实现不使用vector完整代码

以下是使用链表实现Kruskal算法判断回路的C++代码，不使用vector：

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 10005;
const int MAXM = 100005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &e) const {
        return w < e.w;
    }
} e[MAXM];

int n, m, fa[MAXN];

struct Node {
    int v, w;
    int next;
} edge[MAXM << 1];
int head[MAXN], cnt;

void addEdge(int u, int v, int w) {
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) {
        return false;
    }
    fa[fx] = fy;
    return true;
}

bool checkCycle(int u, int fa) {
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) {
            continue;
        }
        if (find(u) == find(v)) {
            return true;
        }
        merge(u, v);
        if (checkCycle(v, u)) {
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    int ans = 0, cnt = 0;
    for (int i = 1; i <= m; ++i) {
        if (merge(e[i].u, e[i].v)) {
            ans += e[i].w;
            addEdge(e[i].u, e[i].v, e[i].w);
            addEdge(e[i].v, e[i].u, e[i].w);
            ++cnt;
        }
        if (cnt == n - 1) {
            break;
        }
    }
    if (checkCycle(1, -1)) {
        cout << "There is a cycle in the graph!" << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}

其中，find函数和merge函数用于实现并查集。checkCycle函数用于判断是否存在环。addEdge函数用于建立边的邻接表。