SRM424 div2 hard

最小全域木を求める。
存在しなかったら空のvectorを返す。
存在したら道の本数がMになるまで付け足す。
UNIONFINDのコードはコピーしたので集合のサイズを求める機能が付いてる。

#include <utility>
#include <set>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

class UNIONFIND
{
	vector<int> date;
	vector<int> scale;
	public:
	UNIONFIND(int n)
	{
		for(int i=0;i<n;i++)
		{
			date.push_back(i);
			scale.push_back(1);
		}
	}
	int root(int n)
	{
		if(date[n]==n)
			return n;
		else
			return date[n]=root(date[n]);
	}
	void unionSet(int x,int y)
	{
		if(root(x)==root(y))
			return;
		scale[root(y)]+=scale[root(x)];
		scale[root(x)]=0;
		date[root(x)]=date[root(y)];
	}
	int unionSize(int n)
	{
		return scale[root(n)];
	}
};


class BestRoads
{
	public:
		vector <int> numberOfRoads(vector <string> input, int M)
		{
			int Rn=0,In=input.size();
			vector<pair<int,int> > road;
			for(int i=0;i<In;i++)
				for(int j=i+1;j<In;j++)
					if(input[i][j]=='Y')
						Rn++,road.push_back(make_pair(i,j));
			vector<bool> used(Rn,false);
			UNIONFIND U(In);
			vector<int> ans(In,0);
			int add=0;

			for(int i=0;i<Rn;i++)
				if(U.root(road[i].first)!=U.root(road[i].second))
				{
					U.unionSet(road[i].first,road[i].second);
					used[i]=true;
					ans[road[i].first]++;
					ans[road[i].second]++;
					add++;
				}
			int id=U.root(0);
			for(int i=0;i<In;i++)
				if(U.root(i)!=id)
					return vector<int>(0);
			if(add==M)
				return ans;
			for(int i=0;i<Rn;i++)
				if(!used[i])
				{
					ans[road[i].first]++;
					ans[road[i].second]++;
					add++;
					if(add==M)
						return ans;
				}
			return vector<int>(0);
		}
};