old_Graph/Minimum_Spanning_Tree_(Kruskal).cpp

• View this file on GitHub
• Last update: 2022-07-19 22:14:43+09:00

Code

long long kruskal(vector<vector<pair<int, int>>> &E){
	int V = E.size();
	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < V; i++){
		for (auto P : E[i]){
			edges.push_back(make_tuple(P.first, i, P.second));
		}
	}
	sort(edges.begin(), edges.end());
	unionfind UF(V);
	long long ans = 0;
	for (auto e : edges){
		int c = get<0>(e);
		int v = get<1>(e);
		int w = get<2>(e);
		if (!UF.same(v, w)){
			UF.unite(v, w);
			ans += c;
		}
	}
	return ans;
}

#line 1 "old_Graph/Minimum_Spanning_Tree_(Kruskal).cpp"
long long kruskal(vector<vector<pair<int, int>>> &E){
	int V = E.size();
	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < V; i++){
		for (auto P : E[i]){
			edges.push_back(make_tuple(P.first, i, P.second));
		}
	}
	sort(edges.begin(), edges.end());
	unionfind UF(V);
	long long ans = 0;
	for (auto e : edges){
		int c = get<0>(e);
		int v = get<1>(e);
		int w = get<2>(e);
		if (!UF.same(v, w)){
			UF.unite(v, w);
			ans += c;
		}
	}
	return ans;
}

Back to top page