culture conference - union find algorithm - use test case 2 to debug and then modify union find algorithm

cultureConference_unionFind_testcase2.cs

#if DEBUG
using Microsoft.VisualStudio.TestTools.UnitTesting;
#endif

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //ProcessInput();
            //RunUnionFind(); 
            RunUnionFindTestCase();
        }

        public static void ProcessInput()
        {
            int n = Convert.ToInt32(Console.ReadLine());
            // Information for employees 1 through n - 1:
            // The first value is the employee's supervisor ID
            // The second value is the employee's burnout status (0 is burned out, 1 is not)
            int[][] e = new int[n - 1][];
            for (int e_i = 0; e_i < n - 1; e_i++)
            {
                string[] e_temp = Console.ReadLine().Split(' ');
                e[e_i] = Array.ConvertAll(e_temp, Int32.Parse);
            }

            long minimumEmployees = RunUnionFind(e);

            Console.WriteLine(minimumEmployees);
        }

        /*
         * Calculate the value of friendships
         */
        public static long RunUnionFind(int[][] edges)
        {
            var unionFind = new UnionFind();

            int count = 0;
            int index = 1;
            bool ceoFound = false;
            foreach (var edge in edges)
            {
                var left = index;
                var right = edge[0];
                var burnout = edge[1];

                if (burnout == 1)
                {
                    continue;
                }

                if (right == 0)
                {
                    ceoFound = true;
                }

                if (unionFind.IsSameGroup(left, right))
                {
                    count++;
                    continue;
                }

                unionFind.Unite(right, left);

                index++;
            }

            var bigThanOne = 0;
            var groups = unionFind.GetGroupsSpecial().Where(v => v != 0).Select(v => v + 1).ToList();

            var original = groups.Sum();
            return (ceoFound) ? (original - 1) : original;
        }

        /// <summary>
        /// 
        /// </summary>
        public static void RunUnionFindTestCase()
        {
            var unionFind = new UnionFind();
            var edges = ReadFile();                            
           
            for (int i = 0; i < edges.Length; i++ )
            {
                var left = i + 1;  // bug found after the contest 
                var current = edges[i];
                var right = current[0];
                var burnout = current[1];

                if (burnout == 1)
                {
                    continue;
                }

                if (unionFind.IsSameGroup(left, right))
                {                    
                    continue;
                }

                unionFind.Unite(right, left);  // put right first, make it parent
            }
            
            var groups = unionFind.GetGroupsSpecial().Where(v => v != 0).Select(v => v + 1).ToList();

            groups.Sort();
            var result = groups.Sum();
        }

        private static int[][] ReadFile()
        {
            string line;
            const string fileName = "D:\\JuliaPersonalFolder\\HackerRank\\cultureConference\\culture-conference-testcases\\input\\input02.txt";

            System.IO.StreamReader file = new System.IO.StreamReader(fileName);

            int n = 0;
            int index = 0;
            var edges = new int[0][];
            while ((line = file.ReadLine()) != null)
            {
                if (index == 0)
                {
                    n = Convert.ToInt16(line);
                    edges = new int[n -1][];
                }
                else
                {
                    if (index - 1 < n - 1)
                    {
                        edges[index - 1] = Array.ConvertAll(line.Split(' '), int.Parse);
                    }
                }

                index++;
            }

            file.Close();

            return edges;
        }
    }    
    
    /// <summary>
    /// Review UnionFind class - 
    /// Modify the UnionFind algorithm - remove path compression 
    /// Add Id for each node
    /// </summary>
    public class UnionFind
    {
        private class Node
        {
            public Node Parent { get; set; }
            public int  Rank   { get; set; }
            public int  Id     { get; set; }

            public HashSet<Node> Children;

            public Node(int id)
            {
                Id = id; // added on May 9, 2017 by Julia Chen
                Children = new HashSet<Node>();
            }
        }

        private Dictionary<object, Node> dictionary = new Dictionary<object, Node>();
       
        private Node FindNode(object data)
        {
            if (!dictionary.ContainsKey(data))
            {
                var node = new Node((int)data);
                dictionary.Add(data, node);
                return node;
            }
            else
            {
                return dictionary[data];
                //return FindRoot(node);
            }
        }

        /// <summary>
        /// find the root of the tree
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private Node FindRoot(Node node)
        {
            if (node.Parent == null)
            {
                return node;
            }
           
            return FindRoot(node.Parent); 
        }

        public void Unite(IComparable x, IComparable y)
        {
            var xNode = FindNode(x);
            var yNode = FindNode(y);
            if (xNode == yNode) return;

            if (xNode.Rank < yNode.Rank)
            {
                ChangeParent(yNode, xNode);
            }
            else
            {
                ChangeParent(xNode, yNode);

                if (xNode.Rank == yNode.Rank)
                {
                    xNode.Rank++;
                }
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="parent"></param>
        /// <param name="childRoot"></param>
        void ChangeParent(Node parent, Node childRoot)
        {
            if (childRoot.Parent != null)
            {
                childRoot.Parent.Children.Remove(childRoot);
            }

            childRoot.Parent = parent;
            childRoot.Parent.Children.Add(childRoot);            
        }

        /// <summary>
        /// IsSameGroup 
        /// it calls Root(Object x) which will create Node object if need. 
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        public bool IsSameGroup(IComparable x, IComparable y)
        {
            return FindNode(x) == FindNode(y);
        }       

        public List<long> GetGroupsSpecial()
        {
            var groups = new List<long>();
            
            foreach (var group in dictionary.Values.Where(d => d.Parent == null))
            {               
               int count = calculatePeopleToConference(group);
               groups.Add(count);                              
            }

            return groups;
        }

        /// <summary>
        /// redirect child to the group leader
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private int calculatePeopleToConference(Node node)
        {
            if (node == null || node.Children.Count == 0) return 0;

            int count = 1;           
            
            foreach (var child in node.Children)
            {
                count += calculatePeopleToConference(child);
            }
            
            return count;
        }
    }

#if DEBUG
    [TestClass]
    public class Test
    {
        [TestMethod]
        public void Tests()
        {           
        }
    }

#endif
}