Kruskal算法

按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。按照选边来构造最小生成树

struct edge
{
	int a, b, v;
	edge(int a,int b,int v): a(a),b(b),v(v){};	
};
class MyCompareq
{
public:
	bool operator()(edge v1, edge v2)const { return v1.v < v2.v; }
};

int find(int x)
{
    if(par[x] != x)
    {
        par[x] = find(par[x]); // 路径压缩 找到后根节点直接赋值
    }
    return par[x];
}
	
set<edge, MyCompare> E; 

int main(int argc, char* argv[])
{

	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		par[i] = i;
	}
	for (int i = 0; i < k; i++)
	{
		int a, b, v;
		cin >> a >> b >> v;
		E.insert(edge(a,b,v));
	}
	vector<pair<int,int>> res;
	for (auto e : E )
	{
        int x = find(e.a);
        int y = find(e.b);
        if(x != y) 
		{
			par[x] = y;
			res.push_back({e.a,e.b});
		}
        else continue;
	}
	for(int i = 0;i<res.size();i++)
	{
		cout << res[i].first << " " << res[i].second << endl;
	}
	return 0;
}