4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct BestRoads
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	vector<int> numberOfRoads(vector<string> roads, int M)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int N = roads.size();
4fd800b3a8 2011-02-23        kinaba: 		vector<int> ans(N);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// Kruskal
4fd800b3a8 2011-02-23        kinaba: 		typedef pair<int,int> road;
4fd800b3a8 2011-02-23        kinaba: 		set<road> Q;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			for(int j=i+1; j<N; ++j)
4fd800b3a8 2011-02-23        kinaba: 				if( roads[i][j]=='Y' )
4fd800b3a8 2011-02-23        kinaba: 					Q.insert( road(i,j) );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector<int> p(N,-1), s(N, 1); // Union-Find
4fd800b3a8 2011-02-23        kinaba: 		int div=N, red=M-N+1;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		for(set<road>::iterator it=Q.begin(); it!=Q.end(); ++it)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			road r = *it;
4fd800b3a8 2011-02-23        kinaba: 			int a=r.first;  while(p[a]!=-1) a=p[a];
4fd800b3a8 2011-02-23        kinaba: 			int b=r.second; while(p[b]!=-1) b=p[b];
4fd800b3a8 2011-02-23        kinaba: 			if( a != b )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				ans[r.first]++, ans[r.second]++, div--;
4fd800b3a8 2011-02-23        kinaba: 				if(s[a]<s[b]) p[a]=b, s[b]+=s[a];
4fd800b3a8 2011-02-23        kinaba: 				else          p[b]=a, s[a]+=s[b];
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			else if( red )
4fd800b3a8 2011-02-23        kinaba: 				ans[r.first]++, ans[r.second]++, red--;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return (red==0 && div==1) ? ans : vector<int>();
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };