报个Google电面面经【更新Union find的解法】

原帖地址:mitbbs

老中面试官,问了个这个题目:

Find all connected components in an undirected graph.

我尝试了DFS和BFS,不知道对不对,最后挂了。
大家有啥好解法?

更新,今天放假,花了点时间回想一下这道题,看了算法书和wiki上union find的部分
,写了个解法,求大神们指点。

Input: int n (node number)
int[][] edges (edges)

public int findClusters(int n, int[][] edges) {
int[] clusters = new int[n];
for (int i=0; i < n; i++) { clusters[i] = -1; } for (int[] edge : edges) { int cluster1 = find(clusters, edge[0]); int cluster2 = find(clusters, edge[1]); if (cluster1 != cluster2) { union(clusters, cluster1, cluster2); } } int cluster_no = 0; for (int i : clusters) { if (clusters[i] == -1) { cluster_no++; } } // Isolated nodes. if (edges.length < n-1) { return cluster_no + n-1-edges.length; } return cluster_no; } private int find(int[] clusters, int n) { if(clusters[n] == -1) { return n; } return find(cluster, clusters[n]); } private void union(int[] clusters, int cluster1, int cluster2) { clusters[cluster1] = cluster2; }