题目
题目链接:
https://www.lintcode.com/problem/629/
思路
核心1:对connections进行排序,根据开销升序排序
核心2:并查集,合并集合,记录下合并的边缘
核心3:如果合并完后,集合数是一个,说明是一棵树,返回边缘集合,否则发你空集合
Java答案
/**
* Definition for a Connection.
* public class Connection {
* public String city1, city2;
* public int cost;
* public Connection(String city1, String city2, int cost) {
* this.city1 = city1;
* this.city2 = city2;
* this.cost = cost;
* }
* }
*/
public class Solution {
/**
* @param connections given a list of connections include two cities and cost
* @return a list of connections from results
*/
public List<Connection> lowestCost(List<Connection> connections) {
//核心1:排序,根据开销排序
Collections.sort(connections,(a,b)->{
if(a.cost == b.cost){
if(a.city1.equals(b.city1)){
return a.city2.compareTo(b.city2);
}else{
return a.city1.compareTo(b.city1);
}
}else{
return a.cost-b.cost;
}
});
UF uf = new UF();
List<Connection> ans = new ArrayList<>();
int mincost=0; //本题中没用,统计最小生成树的最小花开销,比如牛客上相同的题目就是求开销
for (Connection v : connections) {
String f = v.city1;
String t = v.city2;
String f1 = uf.finx(f);
String f2 = uf.finx(t);
if(!f1.equals(f2)){
ans.add(v);
mincost+= v.cost;
uf.union(f,t);
}
}
if(uf.sets==1){ //集合不止一个,说明不能连通
return ans;
}else{
return new ArrayList<>();
}
}
static class UF{
public Map<String,String> parents = new HashMap<>();
public Map<String,Integer> size = new HashMap<>();
public Map<Integer,String> help = new HashMap<>();
int sets =0;
public String finx(String x){
if(!parents.containsKey(x)){
parents.put(x,x);
size.put(x,1);
sets++;
}
int hi=0;
while (!x.equals(parents.get(x))){
help.put(hi++,x);
x= parents.get(x);
}
for(hi--;hi>=0;hi--){
parents.put(help.get(hi),x);
}
return x;
}
public void union(String a,String b){
String f1 = finx(a);
String f2 = finx(b);
if(!f1.equals(f2)){
int s1 = size.get(f1);
int s2 = size.get(f2);
int sum = s1+s2;
if(s1>=s2){
size.put(f1,sum);
parents.put(f2,f1);
}else{
size.put(f2,sum);
parents.put(f1,f2);
}
sets--;
}
}
}
}