http://community.topcoder.com/stat?c=problem_statement&pm=10172&rd=13515
http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm424
这道题目是和最小生成树有关。记得最小生成树的一个算法(容易实现的那个),Kruskal,要用到并查集。想想就是以边为主,那么才可能形成多个边的集合,然后再合并。
并查集的n次合并查找的复杂度是o(n)。TopCoder的思想似乎主要是快速实现解决问题,对复杂度的要求一般,所以这里简单的链式实现就够用了,复杂度是一次合并o(n)(果然比之前好的数据结构复杂度大大增加啊)。
另外返回一个空的数组是直接return new int[]{}就行了。
public class BestRoads { public int[] numberOfRoads(String[] roads, int M) { int N = roads.length; char[][] matrix = new char[N][N]; for (int i = 0; i < N; i++) { matrix[i] = roads[i].toCharArray(); } int id[] = new int[N]; // simple joint-set for (int i = 0; i < N; i++) { id[i] = i; } int deg[] = new int[N]; int CmpCnt = 0; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { if (matrix[i][j] == 'N' || id[i] == id[j]) continue; int idi = id[i]; int idj = id[j]; matrix[i][j] = 'N'; matrix[j][i] = 'N'; deg[i]++; deg[j]++; M--; CmpCnt++; for (int t = 0; t < N; t++) { if (id[t] == idi) id[t] = idj; } } } if (CmpCnt != N-1) return new int[]{}; // not connected; for (int i = 0; i < N && M > 0; i++) { for (int j = i+1; j < N && M > 0; j++) { if (matrix[i][j] == 'Y') { matrix[i][j] = 'N'; matrix[j][i] = 'N'; deg[i]++; deg[j]++; M--; } } } if (M > 0) return new int[]{}; return deg; } }