11631 – Dark roads UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2678

Graphs, kruskal, minimum spanning tree.

How I did it

• Read the number of vertices and edges.
• Read the graph as a Edge list. (node 1 , node 2,weight)
• Call kruskal.
• Calculate all the weight from the graph and substract the minimum cost of the spanning tree.
• Print the value.

Hints

• This algorithm use union find disjoint sets.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define    V        200001
#define    E        200001

using namespace std;

int tree[V];
int rank[V];
long long costoTotal;
struct edge
{
    int from, to;
    int weight;
    bool operator < (const edge &other) const
    {
        return weight < other.weight;
    }
};

vector<edge> edges;

void initialize(int nodes)
{
    int i;
    for(i = 0; i <= nodes; i++)
    {
        tree[i] = i;
        rank[i] = 1;
    }
    edges.clear();
}

int find_set(int element)
{
    if(element != tree[element])
        tree[element] = find_set(tree[element]);
    return tree[element];
}

void union_sets(int x, int y)
{
    int rx, ry;
    rx = find_set(x);
    ry = find_set(y);
    if(rx == ry)
        return;
    if(rank[rx] > rank[ry])
    {
        rank[rx] += rank[ry];
        tree[ry] = rx;
    }
    else
    {
        rank[ry] += rank[rx];
        tree[rx] = ry;
    }
}

int kruskal()//returns the MST weight
{
    int total; //the weight of MST
    int u, v; //vertices in each edge
    int i;
    sort(edges.begin(), edges.end());
    total = 0;
    for(i = 0; i < edges.size(); i++)
    {
        u = find_set(edges[i].from);
        v = find_set(edges[i].to);
        if(u != v)
        {
            union_sets(u,v);
            total += edges[i].weight;
        }
    }
    return total;
}

void read_graph(int number_of_edges)
{
    int i;
    edge e;
    for(i = 0; i < number_of_edges; i++)
    {
        scanf("%d %d %d", &e.from, &e.to, &e.weight);
        costoTotal+= e.weight;
        edges.push_back(e);
    }

}int main()
{
    int nodes;
    int number_of_edges;
    while(scanf("%d %d", &nodes, &number_of_edges))
    {
        if(!nodes && !number_of_edges)
           break;
        costoTotal = 0;
        initialize(nodes);
        read_graph(number_of_edges);
        cout<<costoTotal - kruskal()<<endl;
    }
return 0;
}