Lib/クラスカル法

できること

最小全域木の取得

最大全域木の取得

O(E log V)

UnionFindも合わせて貼る

code:cpp

int kruskal(vector<vector<pair<int,int>>> &ans,vector<vector<pair<int,int>>> &graph){

// need unionfind struct;

//default:最大全域木

int n = graph.size();

vector<pair<int,pair<int,int>>> edges;//{cost,{from,to}}

rep(i,n){

edges.push_back({cost,{i,to}});

}

}

sort(ALL(edges));

reverse(ALL(edges));//ここを外せば最小全域木

UnionFind uf(n);

int cost_sum = 0;

rep(i,edges.size()){

if(!uf.same(from,to)){

cost_sum += cost;

uf.unite(from,to);

}

}

return cost_sum;

}

隠された機能:有向グラフでも無向グラフとして扱っている