Solution for tc srm 356, div2 lvl3

RoadReconstruction.cpp

#include <bits/stdc++.h>
using namespace std;

struct Road {
	string id;
    int x,y;
    int cost;
    Road(string a, int b, int c, int d) : id(a), x(b), y(c), cost(d) {} 
};

bool operator< (const Road& l, const Road& r)  {
    return l.cost < r.cost;
}

class disjoint_sets
{
    vector<int> parent;
    vector<int> rank;
    int nsets;
public:
    disjoint_sets(size_t sz) : parent(sz, -1), rank(sz, -1), nsets(0) {}
	
    int size() {
    	return nsets;
    }
    
    void make_set(int v)
    {
        parent[v] = v;
        rank[v] = 0;
        ++nsets;
    }

    int find_set(int x)
    {
        if (parent[x] != x)
            return parent[x] = find_set(parent[x]);
        return x;
    }

    void union_sets(int l, int r)
    {
        int pl = find_set(l);
        int pr = find_set(r);
        if (pl != pr) {
            --nsets;
            if (rank[pl] < rank[pr])
                swap(pl, pr);
            parent[pr] = pl;
            if (rank[pr] == rank[pl])
                rank[pl] += 1;
        }
    }
};

class RoadReconstruction {
public:
    string selectReconstruction(vector<string> roads) {
    	vector<Road> proads;
        unordered_map<string, int> city2Ind;
        int maxCityInd = 0;
        for (auto s : roads) {
            string id, x, y;
            int cost = 0;
            stringstream(s) >> id >> x >> y >> cost;
            auto itX = city2Ind.find(x);
      		int indX = -1;
			if (itX == city2Ind.end()) {
            	city2Ind.insert( make_pair(x, maxCityInd) );
                indX = maxCityInd;
                ++maxCityInd;
            } else indX = itX->second;
            
            auto itY = city2Ind.find(y);
            int indY = -1;
			if (itY == city2Ind.end()) {
            	city2Ind.insert( make_pair(y, maxCityInd) );
                indY = maxCityInd;
                ++maxCityInd;
            } else indY = itY->second;
            
            proads.push_back( Road(id, indX, indY, cost) );
        }
        sort( proads.begin(), proads.end() );
        disjoint_sets ds(maxCityInd);
        for (int i = 0; i < maxCityInd; ++i)
            ds.make_set(i);
        
        vector<string> res;
        for (int i = 0; i < proads.size(); ++i) {
            if (ds.size() == 1)
                break;
            if (ds.find_set(proads[i].x) != ds.find_set(proads[i].y)) {
                if (proads[i].cost != 0)
                	res.push_back(proads[i].id);
            	ds.union_sets(proads[i].x, proads[i].y);
            }
        }
        if (ds.size() == 1) {
            if (res.size() != 0) {
                sort(res.begin(), res.end());
                stringstream ss;
                for (int i = 0; i < res.size() - 1; ++i)
                    ss << res[i] << ' ';
                ss << res.back();
                return ss.str();
            }
            return "";
        }
        return "IMPOSSIBLE";
    }
};