c++Kruskal算法中判断是否形成回路有很多方法，考虑利用链表实现

Kruskal算法是求解最小生成树的一种贪心算法，它的基本思想是将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入某条边会形成回路，则不加入。

判断是否形成回路是Kruskal算法中的一个重要步骤，我们可以利用并查集来实现。但是，题目中要求利用链表来实现，那么我们可以利用链表的一个特性：每个节点只有一个前驱节点，如果我们能够找到每个节点的祖先节点，就可以判断是否形成回路了。

具体实现方法如下：

首先，我们定义一个结构体Edge表示边，它包含起点、终点和边权重。然后，我们定义一个结构体Node表示节点，它包含一个指向前驱节点的指针prev和一个指向代表集合的节点的指针set。其中，代表集合的节点指向自己，因为每个节点都是一个集合的代表。

struct Edge {
    int u, v, w;
    Edge(int _u, int _v, int _w):u(_u), v(_v), w(_w) {}
};

struct Node {
    Node* prev; //指向前驱节点的指针 
    Node* set; //指向代表集合的节点的指针 
    Node() {
        prev = NULL;
        set = this; //每个节点的代表是自己 
    }
};

接下来，我们定义一个函数findSet，用来查找一个节点所在的集合的代表节点。它的实现方法是不断往前驱节点遍历，直到找到代表节点为止。

Node* findSet(Node* x) {
    while(x->prev != NULL) {
        x = x->prev;
    }
    return x->set;
}

最后，我们定义一个数组node，用来存储每个节点的信息。在Kruskal算法中，我们依次加入边，如果加入某条边会形成回路，则不加入。因此，对于每条边，我们需要先判断它的起点和终点是否在同一个集合中，如果不在，则将它们合并到一个集合中，否则不加入。

int n, m; //n个节点，m条边 
Edge edges[MAXM]; //边的数组 
Node node[MAXN]; //节点的数组 

bool cmp(const Edge& e1, const Edge& e2) { //按边权重从小到大排序 
    return e1.w < e2.w;
}

bool hasCycle(int u, int v) { //判断是否形成回路 
    Node* pu = findSet(&node[u]); //找到u所在的集合的代表节点 
    Node* pv = findSet(&node[v]); //找到v所在的集合的代表节点 
    if(pu == pv) { //如果在同一个集合中，说明形成回路 
        return true;
    }
    else { //否则将它们合并到一个集合中 
        pu->prev = pv;
        pu->set = pv->set; //u所在的集合的代表节点改为v所在的集合的代表节点 
        return false;
    }
}

int kruskal() {
    sort(edges, edges + m, cmp); //按边权重从小到大排序 
    int ans = 0; //最小生成树的权值和 
    for(int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        if(!hasCycle(u, v)) { //如果不形成回路，加入这条边 
            ans += edges[i].w;
        }
    }
    return ans;
}

完整代码如下：