## Monday, October 1, 2012

### SRM356

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

## Tutorials:

### 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
*/

private HashMap<String, Integer> avai;

avai = new HashMap<String, Integer>();

for (int i = 0, index = 0; i < roads.length; i++) {
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) {
} else {
.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)
}
}

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;
}
}

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;
}

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;
}
}
```