Clean C# Disjoint Set solution


  • 1
    K

    The actual logic in the main function is very simple, as long as we have a good data structure (disjoint set) to back it with.
    We simply call union on edge of the edge components for our given edge array.
    At the end, we can count the number of connected components, and add any nodes in the original number of nodes that are not in the final disjoint set (because they were not in any of the given edges).

    Note: We could also add the given nodes inside the "Union" function as, if you were to call union in two nodes, you would expect them to be in the set first.

    public int CountComponents(int numNodes, int[,] edges) {
        DisjointSet set = new DisjointSet();
        for (int i = 0; i < edges.GetLength(0); i++) {
            set.Add(edges[i, 0]);
            set.Add(edges[i, 1]);
            
            set.Union(edges[i, 0], edges[i, 1]);
        }
        
        return set.NumRoots + numNodes - set.NumNodes;
    }
    
    public class DisjointSet {
        private Dictionary<int, int> _parents = new Dictionary<int, int>();
        
        public int NumRoots { get; private set; }
        public int NumNodes { get; private set; }
        
        public void Add(int x) {
            // Don't add to set if it already is there.
            if (this._parents.ContainsKey(x)) {
                return;
            }
            
            this._parents[x] = x;
            this.NumRoots++;
            this.NumNodes++;
        }
        
        public int GetRoot(int x) {
            if (this._parents[x] == x) {
                return x;
            }
            
            return this.GetRoot(this._parents[x]);
        }
        
        public void Union(int x, int y) {
            int xRoot = this.GetRoot(x);
            int yRoot = this.GetRoot(y);
            
            if (xRoot == yRoot) {
                return;
            }
            
            // We are joining two existing nodes.
            // Reducing the number of non connected components by one.
            this.NumRoots--;
            this._parents[yRoot] = xRoot;
        }
    }
    

  • 0

    Very Good Disjoint set. A small improvement on GetRoot method:
    From a linear time to logarithmic time. N: Depth of level

            public int GetRoot(int x)
            {
                while (x != this._parents[x])
                {
                    _parents[x] = _parents[_parents[x]];  //Make every other node in the path point to its grandparent(thereby halving path length)
                    
                    x = _parents[x];
                }
                return x;
            }
    

  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.