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

Kruskal算法是一种经典的最小生成树算法，它的核心思想是将图中的所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入某条边会形成回路，则不加入该边。判断是否形成回路的方法有很多，下面介绍一种基于链表的方法。

我们可以用一个链表来维护当前已经加入生成树的边，每次加入一条新边时，检查该边的两个端点是否在同一个链表中，如果是，则加入该边会形成回路，不加入；否则，加入该边，并将两个端点所在的链表合并成一个链表。

下面是基于链表的Kruskal算法的代码：

const int MAXN = 1000;
int n; // 节点数
struct Edge {
    int u, v, w;
    bool operator<(const Edge& e) const {
        return w < e.w;
    }
} edges[MAXN];
int parent[MAXN]; // 并查集
int head[MAXN], nxt[MAXN], to[MAXN], idx = 0; // 链表
int cnt = 0; // 边数

int find(int x) { // 并查集查找根节点
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void merge(int x, int y) { // 并查集合并
    int px = find(x), py = find(y);
    if (px != py) {
        parent[px] = py;
    }
}

void addEdge(int u, int v) { // 添加边到链表
    to[++idx] = v;
    nxt[idx] = head[u];
    head[u] = idx;
}

void kruskal() {
    // 初始化并查集和链表
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    memset(head, -1, sizeof(head));
    // 将边按权值排序
    sort(edges, edges+cnt);
    // 构建生成树
    for (int i = 0; i < cnt; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) { // 未形成回路
            merge(u, v);
            addEdge(u, v);
            addEdge(v, u);
            cout << u << " " << v << " " << w << endl;
        }
    }
}

int main() {
    // 输入边
    cin >> n >> cnt;
    for (int i = 0; i < cnt; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    kruskal();
    return 0;
}

在上面的代码中，我们使用了一个 `Edge` 结构体来存储边的信息，包括起点、终点和权值。我们还定义了一个并查集 `parent`，用来判断加入一条新边是否会形成回路。同时，我们使用了一个链表来维护当前已经加入生成树的边，每个节点 `i` 的链表中存储的是与节点 `i` 相连的边的终点 `j`。

在 `kruskal` 函数中，我们首先将边按照权值从小到大排序，然后依次加入到生成树中。对于每条边 `(u,v,w)`，如果它的起点和终点不在同一个连通块中，则将它加入到生成树中，并将起点和终点所在的链表合并成一个链表。