Hackerrank week code 28 - value of friendship - code review - with unit test - study more and post a code review on stackexchange.com

valueOfFriendship_codereview_testcase.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;

namespace ConsoleApplication1
{
    /*
     * Code study: yambe2002
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            var queries = Int32.Parse(Console.ReadLine());
            while (queries > 0)
            {
                var summaryRow = Console.ReadLine().Split();

                var studentsTotal = Int32.Parse(summaryRow[0]);
                var friendshipsTotal = Int32.Parse(summaryRow[1]);

                var friendShips = new List<Tuple<int, int>>();

                for (int i = 0; i < friendshipsTotal; i++)
                {
                    var friendshipRow = Console.ReadLine().Split();
                    friendShips.Add(new Tuple<int, int>(Int32.Parse(friendshipRow[0]), Int32.Parse(friendshipRow[1])));
                }

                Console.WriteLine(CalculateValueOfFriendships(studentsTotal, friendShips));

                queries--;
            }
        }

        /*
         * Calculate the value of friendships
         */
        public static long CalculateValueOfFriendships(int n, List<Tuple<int, int>> friends)
        {
            long totalValueOfFriendship = 0;

            var unionFind = new UnionFind();

            var relationCreatingClosedLoopNum = 0;
            foreach (var friend in friends)
            {
                if (unionFind.IsSameGroup(friend.Item1, friend.Item2))
                {
                    relationCreatingClosedLoopNum++;
                    continue;
                }

                unionFind.Unite(friend.Item1, friend.Item2);
            }

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

            groups.Sort();
            groups.Reverse();

            long currentVal = 0;
            foreach (var g in groups)
            {
                currentVal += g * (g - 1);
            }

            totalValueOfFriendship = currentVal;
            totalValueOfFriendship += currentVal * relationCreatingClosedLoopNum;

            while (groups.Count() > 0)
            {
                var num = groups.Last();
                groups.RemoveAt(groups.Count() - 1);

                currentVal = 0;
                foreach (var g in groups)
                {
                    currentVal += g * (g - 1);
                }

                totalValueOfFriendship += currentVal * (num - 1);

                num--;
                while (num > 1)
                {
                    totalValueOfFriendship += num * (num - 1);
                    num--;
                }
            }

            return totalValueOfFriendship;
        }
    }

    /*
     * Class UnionFind 
     * 
     */
    public class UnionFind
    {
        private class Node
        {
            public Node Parent { get; set; }
            public int Rank { get; set; }

            public HashSet<Node> Children;

            public Node()
            {
                Children = new HashSet<Node>();
            }
        }

        private Dictionary<object, Node> _dict = new Dictionary<object, Node>();

        private Node Root(object data)
        {
            if (!_dict.ContainsKey(data))
            {
                var node = new Node();
                _dict.Add(data, node);
                return node;
            }
            else
            {
                var node = _dict[data];
                return Find(node);
            }
        }

        private Node Find(Node node)
        {
            if (node.Parent == null)
            {
                return node;
            }

            return node.Parent = Find(node.Parent);
        }

        public void Unite(IComparable x, IComparable y)
        {
            var xRoot = Root(x);
            var yRoot = Root(y);
            if (xRoot == yRoot) return;

            if (xRoot.Rank < yRoot.Rank)
            {
                ChangeParent(yRoot, xRoot);
            }
            else
            {
                ChangeParent(xRoot, yRoot);

                if (xRoot.Rank == yRoot.Rank)
                {
                    xRoot.Rank++;
                }
            }
        }

        /*
         * write something here...
         */
        void ChangeParent(Node parent, Node childRoot)
        {
            if (childRoot.Parent != null)
            {
                childRoot.Parent.Children.Remove(childRoot);
            }

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

            foreach (var child in childRoot.Children.ToList())
            {
                ChangeParent(parent, child);
            }
        }

        public bool IsSameGroup(IComparable x, IComparable y)
        {
            return Root(x) == Root(y);
        }

        public List<long> GetGroups()
        {
            var groups = new List<long>();

            foreach (var group in _dict.Values.Where(d => d.Parent == null))
            {
                groups.Add(group.Children.Count());
            }

            return groups;
        }
    }

#if DEBUG
    [TestClass]
    public class Test
    {
        [TestMethod]
        public void Tests()
        {
            // sample case => 32
            //1
            //5 4
            //1 2
            //3 2
            //4 2
            //4 3
            // 12 -> 12 -> 6 -> 2
            var n = 5;
            var m = 4;
            var friends = new List<Tuple<int, int>>
            {
                new Tuple<int, int>(1, 2),
                new Tuple<int, int>(3, 2),
                new Tuple<int, int>(4, 2),
                new Tuple<int, int>(4, 3),
            };

            Assert.AreEqual(32, Program.CalculateValueOfFriendships(n, friends));

            n = 7;
            m = 7;
            friends = new List<Tuple<int, int>>
            {
                new Tuple<int, int>(1, 2),
                new Tuple<int, int>(3, 2),
                new Tuple<int, int>(3, 4),
                new Tuple<int, int>(4, 2),
                new Tuple<int, int>(1, 4),
                new Tuple<int, int>(5, 6),
                new Tuple<int, int>(5, 7),
            };

            Assert.AreEqual(88, Program.CalculateValueOfFriendships(n, friends));
        }

        [TestMethod]
        public void RandomTest()
        {
            var randomNumber = new Random();

            //var n = rnd.Next() % 100000 + 1;
            var n = 100000;
            var m = Math.Min(n * (n - 1) / 2, 200000);

            var friends = new List<Tuple<int, int>>();

            for (int i = 0; i < m; i++)
            {
                friends.Add(new Tuple<int, int>(randomNumber.Next() % n + 1, randomNumber.Next() % n + 1));
            }

            var valueOfFriendships = Program.CalculateValueOfFriendships(n, friends);

            Assert.IsTrue(true);
        }
    }

#endif
}