Program in c or java

general
1

Given String[] roads, each element of which describes a single road. Damaged roads are formatted as “id city1 city2 cost” and non damaged roads are formatted as “id city1 city2”. In this notation id is the unique identifier of the road and city1 and city2 are the case sensitive names of two cities directly connected by that road. If the road is damaged cost represents the price of rebuilding that road. Each id will be formatted “Cx” where C is an uppercase letter and x is a digit . Every city in the country will appear atleast once in roads. Write a program that return a string containing a single space separated list of the identifier of the roads that must be rebuilt to achieve your goal. If there are multiple possibilities select the one with the minimum total reconstruction cost.

2

I hope this will help you, but make sure next time you should ask a better question not this copy paste.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
#include <set>
#include <map>
 
using namespace std;
 
#define TRACE(x...) 
#define WATCH(x...) TRACE( cout << #x " = " << x << "\n" )
#define PRINT(x...) TRACE( printf (x) )
 
#define REP(i, x) for (int i = 0; i < x; ++i)
#define FOR(i, x, y) for (int i = x; i < y; ++i)
#define FORE(i, x) for (typeof(x.begin()) i = x.begin(); i != x.end(); i++)
 
#define SZ(x) int(x.size())
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
 
int tam[110];
int label[110];
 
class RoadReconstruction {
 
  public:
  
  void unionSet (int a, int b) {
    if (tam[a] < tam[b]) {
      tam[b] += tam[a];
      tam[a] = 1;
      label[a] = label[b];
    }
    else {
      tam[a] += tam[b];
      tam[b] = 1;
      label[b] = label[a];
    }
  }
  
  int findSet (int x) {
    if (x != label[x])
      label[x] = findSet(label[x]);
    return (label[x]);
  }
  
  string selectReconstruction (vector <string> r) {
    string ret = "";
    vector <string> aux;
    string orig, dest, id;
    map <string, int> m;
    int cid = 0;
    int cost;
    int add = 0;
    vector <pair <int, int> > ok;
    vector <pair <int, pair <string, pair <int, int> > > > edges;
    
    sort(ALL(r));
    int n = SZ(r);
    
    REP(i, n) {
      istringstream iss(r[i]);
      cost = 0;
      iss >> id;
      iss >> orig;
      iss >> dest;
      iss >> cost;
      if (m.find(orig) == m.end())
        m[orig] = cid++;
      if (m.find(dest) == m.end())
        m[dest] = cid++;
        
      WATCH(id);
      WATCH(orig);
      WATCH(dest);
      WATCH(cost);
      
      if (cost == 0) {
        ok.PB(MP(m[orig], m[dest]));
      }
      else {
        edges.PB(MP(cost, MP(id, MP(m[orig], m[dest]))));
      }
    }
    sort(ALL(edges));
    REP(i, cid) {
      tam[i] = 1;
      label[i] = i;
    }

    REP(i, SZ(ok)) {
      int u = ok[i].first;
      int v = ok[i].second;
      findSet(u);
      findSet(v);
      if (label[u] != label[v]) {
        unionSet(label[u], label[v]);
        add++;
      }
    }
 

    for (int i = 0; i < SZ(edges) && add < cid - 1; ++i) {
      int u = edges[i].second.second.first;
      int v = edges[i].second.second.second;
      findSet(u);
      findSet(v);
      if (label[u] != label[v]) {
        unionSet(label[u], label[v]);
        add++;
        aux.PB(edges[i].second.first);
      }
    }
    sort(ALL(aux));
    REP(i, SZ(aux)) {
      if (i)
        ret += " ";
      ret += aux[i];
    }
    if (add == cid - 1)
      return (ret);
    return ("IMPOSSIBLE");
  }
  
};