C# | First practice | Union Find algorithm | Timeout on 8/12 test case | March 24, 2021

March 24, 2021

Here is the link.

C# | First practice | Union Find algorithm | Timeout on 8/12 test case | March 24, 2021

March 24, 2021
Introduction
It is the second algorithm in Amazon mock online code screen. I like to try to solve the algorithm using union find algorithm, brute force every edge in connection argument, and then check how many disjoint set if the edge is removed.

Timeout challenge
My idea failed to pass test case 8/ 12 cases. One of ideas is to prune the algorithm to expedite the search.

public class Solution {
     /// <summary>
        /// March 24, 2021
        /// The idea is to use union find algorithm, and go over each edge, determine if 
        /// the edge is removed, then count of disjoint sets is one or not. 
        /// n - nodes in network, 1 to 10^5 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="connections"></param>
        /// <returns></returns>
        public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections)
        {
            if (n <= 0 || connections == null || connections.Count == 0)
            {
                return new List<IList<int>>(); 
            }

            var length = connections.Count;
            var paths = new List<IList<int>>(); 

            for (int i = 0; i < length; i++)
            {
                var count = unionFindDisjointSetCount(n, connections, i);
                if (count > 1)
                {
                    paths.Add(connections[i]); 
                }
            }

            return paths; 
        }

        /// <summary>
        /// Union find algorithm
        /// remove one edge - count disjoint sets 
        /// </summary>
        /// <returns></returns>
        private static int unionFindDisjointSetCount(int n, IList<IList<int>> connections, int removed)
        {
            var parents = new int[n];

            for (int i = 0; i < n; i++)
            {
                parents[i] = i; 
            }

            var length = connections.Count;
            for (int i = 0; i < length; i++)
            {
                if (i == removed)
                {
                    continue;
                }

                var edge = connections[i];
                var end1 = edge[0];
                var end2 = edge[1];
                var max = Math.Max(end1, end2);
                var min = Math.Min(end1, end2);

                parents[FindParents(parents, max)] = FindParents(parents, min);
            }

            // go over all the nodes again
            var rootNodeCount = 0; 
            for (int i = 0; i < n; i++)   // Do not mix length with n; should be n, not length
            {
                parents[i] = FindParents(parents, i);               
            }

            // check last moment 
            for (int i = 0; i < n; i++)
            {
                if (parents[i] == i)
                {
                    rootNodeCount++;
                }
            }

            return rootNodeCount; 
        }

        /// <summary>
        /// union find algorithm
        /// path compression 
        /// </summary>
        /// <param name="parents"></param>
        /// <param name="node"></param>
        /// <returns></returns>
        private static int FindParents(int[] parents, int node)
        {
            if (parents[node] == node)
            {
                return node; 
            }

            parents[node] = FindParents(parents, parents[node]);
            return parents[node];
        }
}

public class Solution {
     /// <summary>
        /// March 24, 2021
        /// The idea is to use union find algorithm, and go over each edge, determine if 
        /// the edge is removed, then count of disjoint sets is one or not. 
        /// n - nodes in network, 1 to 10^5 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="connections"></param>
        /// <returns></returns>
        public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections)
        {
            if (n <= 0 || connections == null || connections.Count == 0)
            {
                return new List<IList<int>>(); 
            }

            var length = connections.Count;
            var paths = new List<IList<int>>(); 

            for (int i = 0; i < length; i++)
            {
                var count = unionFindDisjointSetCount(n, connections, i);
                if (count > 1)
                {
                    paths.Add(connections[i]); 
                }
            }

            return paths; 
        }

        /// <summary>
        /// Union find algorithm
        /// remove one edge - count disjoint sets 
        /// </summary>
        /// <returns></returns>
        private static int unionFindDisjointSetCount(int n, IList<IList<int>> connections, int removed)
        {
            var parents = new int[n];

            for (int i = 0; i < n; i++)
            {
                parents[i] = i; 
            }

            var length = connections.Count;
            for (int i = 0; i < length; i++)
            {
                if (i == removed)
                {
                    continue;
                }

                var edge = connections[i];
                var end1 = edge[0];
                var end2 = edge[1];
                var max = Math.Max(end1, end2);
                var min = Math.Min(end1, end2);

                parents[FindParents(parents, max)] = FindParents(parents, min);
            }

            // go over all the nodes again
            var rootNodeCount = 0; 
            for (int i = 0; i < n; i++)   // Do not mix length with n; should be n, not length
            {
                parents[i] = FindParents(parents, i);               
            }

            // check last moment 
            for (int i = 0; i < n; i++)
            {
                if (parents[i] == i)
                {
                    rootNodeCount++;
                }
            }

            return rootNodeCount; 
        }

        /// <summary>
        /// union find algorithm
        /// path compression 
        /// </summary>
        /// <param name="parents"></param>
        /// <param name="node"></param>
        /// <returns></returns>
        private static int FindParents(int[] parents, int node)
        {
            if (parents[node] == node)
            {
                return node; 
            }

            parents[node] = FindParents(parents, parents[node]);
            return parents[node];
        }
}