roads_and_libraries.cpp

/*
 * Author : thesigmaguy
 * Date : 31/Oct/2019
 * Problem : Libraries and Roads (using Disjoint Set Union)
 */
#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the roadsAndLibraries function below.
int find_parent(int ind, vector<pair<int, long long>>& parent)
{
    vector<int> child;
    while(ind != parent[ind].first)
    {
        child.push_back(ind);
        ind=parent[ind].first;
    }
    for(auto i:child)
        parent[i].first = ind;
    return ind;
}

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) 
{
    vector<pair<int, long long>> parent;
    for(int i=0;i<=n;i++)
    {
        parent.push_back(make_pair(i,1));
    }
    for(int i=0;i<cities.size();i++)
    {
        int p1 = find_parent(cities[i][0],parent);
        int p2 = find_parent(cities[i][1],parent);
        if(p1!=p2)
        {
            if(parent[p1].second >= parent[p2].second)
            {
                parent[p2].first = p1;
                parent[p1].second += parent[p2].second;
            }
            else
            {
                parent[p1].first = p2;
                parent[p2].second += parent[p1].second;
            }
        }
    }
    long sum =0;
    for(int i=1;i<=n;i++)
    {
        if(parent[i].first == i)
        {
	    //Either make all libraries or make one library and (nodes-1) roads
            sum += min((long long)c_lib + c_road*((long long)parent[i].second-1), parent[i].second*(long long)c_lib);
        }
    }
    return sum;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int q;
    cin >> q;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string nmC_libC_road_temp;
        getline(cin, nmC_libC_road_temp);

        vector<string> nmC_libC_road = split_string(nmC_libC_road_temp);

        int n = stoi(nmC_libC_road[0]);

        int m = stoi(nmC_libC_road[1]);

        int c_lib = stoi(nmC_libC_road[2]);

        int c_road = stoi(nmC_libC_road[3]);

        vector<vector<int>> cities(m);
        for (int i = 0; i < m; i++) {
            cities[i].resize(2);

            for (int j = 0; j < 2; j++) {
                cin >> cities[i][j];
            }

            cin.ignore(numeric_limits<streamsize>::max(), '\n');
        }

        long result = roadsAndLibraries(n, c_lib, c_road, cities);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}