MinimumSpanningTree.sublime-snippet

<snippet>
	<content><![CDATA[
class FindingMST{
	int n;
	vector<int> id;
	public:
	void init(int n){
		this->n = n;
		id.assign(n+1,0);
		for(int i=0;i<=n;i++){
			id[i] = i;
		}
	}
	int root(int x){
		while(x != id[x]){
			id[x] = id[id[x]];
			x = id[x];
		}
		return x;
	}
	void uni(int u,int v){
		u = root(u);
		v = root(v);
		id[v] = u;
	}
	int kruskal(vector<pair<int,pair<int,int>>> graph,vector<pair<int,int>> MST[]){
		int cost = 0;
		sort(graph.begin(),graph.end());
		for(auto &x : graph){
			int u = x.second.first;
			int v = x.second.second;
			if(root(u) != root(v)){
				uni(u,v);
				cost += x.first;
				MST[u].push_back({x.first,v});
				MST[v].push_back({x.first,u});
			}
		}
		return cost;
	}
};
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>mst</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>