Minimum Spanning Tree

kruskal.cpp

template<typename T>
class kruskal{
	static const int MAXN=100005;
	int n; // 1-base
	tuple<T,int,int> edge;
	int pa[MAXN];
	int find(int x){
		if(x==pa[x]) return x;
		return pa[x] = find(pa[x]);
	}
public:
	void init(int _n){
		n = _n;
	}
	void addEdge(int u,int v,const T &cost){
		edge.emplace_back(cost, u, v);
	}
	pair<T,int> solve(){
		T ans = 0;
		int component = n;
		for(int i=1; i<=n; ++i) pa[i] = i;
		sort(edge.begin(), edge.end());
		for(const auto &e: edge){
			int u = find(get<1>(e)), v = find(get<2>(e));
			if(u==v) continue;
			pa[u] = v;
			ans += get<0>(e);
		}
		return {ans, component};
	}
};

prim.cpp

template<typename T>
class prim{
	static const int MAXN=100005;
	struct edge{
		int u, v;
		T cost;
		edge(){}
		edge(int u,int v,const T &cost):u(u),v(v),cost(cost){}
		bool operator< (const edge&b)const{
			return cost > b.cost;
		}
	};
	int n;// 1-base
	vector<edge> E;
	vector<int> G[MAXN];
	bool vis[MAXN];
	T build(int x){
		T ans = 0;
		priority_queue<edge> q;
		for(auto i: G[x]) q.push(E[i]);
		vis[x] = true;
		while(q.size()){
			edge e = q.top(); q.pop();
			if(vis[e.v]) continue;
			ans += e.cost;
			vis[e.v] = true;
			for(auto i:G[e.v]) if(!vis[E[i].v]){
				q.push(E[i]);
			}
		}
		return ans;
	}
public:
	void init(int _n){
		n = _n;
		for(int i=1; i<=n; ++i) G[i].clear();
	}
	void addEdge(int u, int v, const T &cost){
		G[u].emplace_back(E.size());
		E.emplace_back(u, v, cost);
		G[v].emplace_back(E.size());
		E.emplace_back(v, u, cost);
	}
	pair<T,int> solve(){
		T ans = 0;
		int component = 0;
		for(int i=1; i<=n; ++i) vis[i] = false;
		for(int i=1; i<=n; ++i) if(!vis[i]){
			ans += build(i);
			++component;
		}
		return {ans, component};
	}
};