简单的思路

跑第一遍Kruskal的时候，给生成树的边都打上标记。

然后在跑第二遍的时候，在同等权值的条件下，让打了标记的排在后面（重新sort一遍即可）。

这样如果把没有打标记的边放入生成树的话，就说明生成树不唯一

class Edge
{
int weight;
int flag;
int u;
int v;
}

bool cmp(Edge &e1, Edge &e2)
{
    if(e1.weight != e2.weight) return e1.weight < e2.weight;
    return e1.flag < e2.flag;
}

• Re:给个只用跑两次Kruskal的算法 (352) Gitfan 2017-02-25 20:44:22