Leetcode 323 - Union-Find bug 求解

原题如下：Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

感觉非常直观的一道Union-Find的题目，但是有一个test case 中的输出值竟然为负数，百思不得其解，求大神提点我一下哪里出了问题，谢谢。

代码如下：

1. public class Solution {
   
2.     public int CountComponents(int n, int[][] edges) {
   
3.         UnionFind uf = new UnionFind(n);
   
4.         for(int i=0; i<edges.Length; i++)
   
5.         {
   
6.             uf.Union(edges[i][0], edges[i][1]);   
   
7.         }
   
8.         return uf.Count();
   
9.     }
   
10. }
    
11. 
    
12. public class UnionFind{
    
13.     private int count;
    
14.     private int[] arr;
    
15.     private int[] sizes;
    
16.     public UnionFind(int n){
    
17.         count = n;
    
18.         arr = new int[n];
    
19.         sizes = new int[n];
    
20.         for(int i=0; i<n; i++){
    
21.             arr[i] = i;
    
22.             sizes[i] = 1;
    
23.         }
    
24.     }
    
25.    
    
26.     public int Count(){
    
27.         return count;
    
28.     }
    
29.    
    
30.     public bool Connected(int p, int q){
    
31.         return Find(p)==Find(q);
    
32.     }
    
33.    
    
34.     public bool Union(int p, int q){
    
35.         int val_p = Find(p);
    
36.         int val_q = Find(q);
    
37.         if(val_p==val_q) return false;
    
38.         
    
39.         if(sizes[val_p]>sizes[val_q]){
    
40.             arr[q] = val_p;
    
41.             sizes[val_p]+=sizes[val_q];
    
42.         }
    
43.         else{
    
44.             arr[p] = val_q;
    
45.             sizes[val_q]+=sizes[val_p];
    
46.         }
    
47.         
    
48.         count--;
    
49.         return true;
    
50.     }
    
51.    
    
52.     private int Find(int p){
    
53.         while(p!=arr[p]){
    
54.             p = arr[p];
    
55.         }
    
56.         return p;
    
57.     }
    
58. }

复制代码

40行和44行不对。应该是arr[val_q] = val_q。另外，你的uf没加path compression。可能会比较慢。

不知道小帅 发表于 2020-9-8 10:51
40行和44行不对。应该是arr[val_q] = val_q。另外，你的uf没加path compression。可能会比较慢。

非常感谢，终于找到bug了。。。