SRM356

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

Source Code:

---

Sivision Two - Level Three:

Solution

This is a Minimum Spanning Tree problem, which here is solved by using Union-Find algorithm, The only meaning thing in this disjoint-set data structure is parant[x], to identify if they are in the same group.
The algorithm first collects all of the roads, then sorts them by cost and ID name as described in the statement, go through every road and check if the two connected cities are in the same group, if not, we get them in the same group by using union(x,y) function.
At last, we need to check if every city is in the same group to show if this mission is possible to be finished.
At the very last, every rebuild road ID needs to be sorted.

Source Code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: antonio081014
 */

public class RoadReconstruction {

    private HashMap<String, Integer> avai;

    public String selectReconstruction(String[] roads) {
 ArrayList<Road> list = new ArrayList<Road>();
 avai = new HashMap<String, Integer>();

 for (int i = 0, index = 0; i < roads.length; i++) {
     String[] str = roads[i].split(" ");
     int a, b;
     if (avai.get(str[1]) == null) {
  a = index++;
  avai.put(str[1], a);
     } else
  a = avai.get(str[1]);

     if (avai.get(str[2]) == null) {
  b = index++;
  avai.put(str[2], b);
     } else
  b = avai.get(str[2]);

     if (str.length == 3) {
  list.add(new Road(str[0], str[1], str[2], 0));
     } else {
  list.add(new Road(str[0], str[1], str[2], Integer
   .parseInt(str[3])));
     }
 }

 Collections.sort(list);

 UnionFind set = new UnionFind(100);
 List<String> retList = new ArrayList<String>();

 for (int i = 0; i < list.size(); i++) {
     String id = list.get(i).id;
     String c1 = list.get(i).city1;
     String c2 = list.get(i).city2;
     int a = avai.get(c1);
     int b = avai.get(c2);
     if (set.find(a) != set.find(b)) {
  set.union(a, b);
  if (list.get(i).cost != 0)
      retList.add(id);
     }
 }

 for (Map.Entry<String, Integer> entry : avai.entrySet()) {
     // System.out.println(entry.getKey());
     // System.out.println(entry.getValue());
     if (set.find(entry.getValue()) != set.find(0))
  return "IMPOSSIBLE";
 }

 if (retList.size() == 0)
     return "";
 Collections.sort(retList);
 String ret = retList.get(0);
 for (int i = 1; i < retList.size(); i++)
     ret += " " + retList.get(i);
 return ret;
    }
}

class Road implements Comparable<Road> {
    public String id;
    public String city1;
    public String city2;
    public int cost;

    public Road(String id, String c1, String c2, int cost) {
 this.id = id;
 this.city1 = c1;
 this.city2 = c2;
 this.cost = cost;
    }

    public int compareTo(Road a) {
 if (this.cost != a.cost)
     return this.cost - a.cost;
 return this.id.compareTo(a.id);
    }
}

class UnionFind {
    int N;
    int[] parent;

    public UnionFind(int n) {
 this.N = n;
 parent = new int[n];

 for (int i = 0; i < n; i++) {
     parent[i] = i;
 }
    }

    public int find(int x) {
 if (parent[x] == x)
     return x;
 return parent[x] = find(parent[x]);
    }

    public void union(int x, int y) {
 int r1 = find(x);
 int r2 = find(y);
 if (r1 == r2)
     return;
 parent[r1] = r2;
    }
}

---

Division Two - Level Two:

Solution

Source Code:

---

Division Two - Level One:

Solution

Source Code: