Hackerrank week of code 28 - study code -

valueofFriendship_studycode1.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
{
    class Program
    {
        static void Main(string[] args)
        {
            var t = Int32.Parse(Console.ReadLine());
            while (t > 0)
            {
                var s = Console.ReadLine().Split();
                var n = Int32.Parse(s[0]);
                var m = Int32.Parse(s[1]);
                var friendShips = new List<Tuple<int, int>>();
                for (int i = 0; i < m; i++)
                {
                    s = Console.ReadLine().Split();
                    friendShips.Add(new Tuple<int, int>(Int32.Parse(s[0]), Int32.Parse(s[1])));
                }

                Console.WriteLine(GetAns(n, friendShips));

                t--;
            }
        }

        public static long GetAns(int n, List<Tuple<int, int>> friends)
        {
            long ret = 0;

            var unionFind = new UnionFind();

            var relationCreatingClosedLoopNum = 0;
            foreach (var f in friends)
            {
                if (unionFind.IsSameGroup(f.Item1, f.Item2))
                {
                    relationCreatingClosedLoopNum++;
                    continue;
                }
                unionFind.Unite(f.Item1, f.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);
            }

            ret = currentVal;
            ret += 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);
                }
                ret += currentVal * (num - 1);

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

            return ret;
        }
    }

    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++;
            }
        }

        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 ret = new List<long>();

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

            return ret;
        }
    }

#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.GetAns(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.GetAns(n, friends));
        }

        [TestMethod]
        public void RandomTest()
        {
            var rnd = 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>(rnd.Next() % n + 1, rnd.Next() % n + 1));
            }
            var result = Program.GetAns(n, friends);
            Assert.IsTrue(true);
        }
    }
#endif
}