C#: Easy to Understand Algorithm with Explanation. (Accepted)


  • 1

    0_1521955956422_85d148cc-f557-438a-bebb-c6d17f5171a3-image.png
    A graph is a valid tree when it satisfies the following two conditions:

    1. There is no cycle in the graph.
    2. Every node is reached (has to be a connected graph)

    My solution is based on the Union-Find algorithm
    You can learn more about the Union-Find algorithm here.

    Solution 1: Exact representation (template) of the algorithm.

    public class Solution {
        int[] parent;
        public bool ValidTree(int n, int[,] edges)
        {
            int edgeCount = edges.Length / 2;
            //An undirected tree with n nodes must have exactly n−1 edges.
            if (edgeCount != n - 1)
                return false;
            //Initializing parent to -1 for all vertices.
            this.parent = new int[n];
            for (int i = 0; i < n; i++)
                this.parent[i] = -1;
            for (int i = 0; i < edgeCount; i++)
            {
                //Extracting vertices of an edge.
                int elementOne = edges[i, 0];
                int elementTwo = edges[i, 1];
                //Find
                if (Find(elementOne) == Find(elementTwo))
                    return false;
                else
                    Union(elementOne, elementTwo);   //Union
            }
            return true;
        }
        private int Find(int element)
        {
            if (this.parent[element] == -1)
                return element;
            else
                return Find(this.parent[element]);
        }
        private void Union(int elementOne, int elementTwo)
        {
            int parentOne = Find(elementOne);
            int parentTwo = Find(elementTwo);
            parent[parentOne] = parentTwo;
        }
    }
    

    Solution 2: Cleaner/Optimized version of above algorithm.

    public class Solution {
        int[] parent;
        public bool ValidTree(int n, int[,] edges) {
            int edgeCount = edges.Length / 2;
            //An undirected tree with n nodes must have exactly n−1 edges.
            if (edgeCount != n - 1)
                return false;
            //Initializing parent to -1 for all vertices.
            this.parent = new int[n];
            for (int i = 0; i < n; i++)
                this.parent[i] = -1;
            for (int i = 0; i < edgeCount; i++)
            {
                //Extracting vertices of an edge.
                int elementOne = edges[i, 0];
                int elementTwo = edges[i, 1];
                //Find
                int parentOne = Find(elementOne);
                int parentTwo = Find(elementTwo);
                if (parentOne == parentTwo)
                    return false;
                else
                    this.parent[parentOne] = parentTwo;     //Union
            }
            return true;
        }    
        private int Find(int element)
        {
            if (this.parent[element] == -1)
                return element;
            else
                return Find(this.parent[element]);
        }
    }
    

Log in to reply
 

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