Hackerrank week code 28 - study code

valueOfFriendship_studycode5.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;


namespace Solution
{
    /*
     * Study C# code and review by Jianmin Chen
     * January 19, 2017
     */
    class Program
    {
        static void Main(string[] args)
        {           
            using (var provider = new InputProvider("test.txt"))
            {
                new Solution(provider);
            }
            
            Console.ReadKey();
        }

        public class Solution
        {
            public Solution(IInputProvider provider)
            {
                int queries = provider.GetNextInt32();

                for (int query = 0; query < queries; query ++)
                {
                    int[] summaryRow = provider.GetArray(int.Parse);

                    var unionFind    = new UnionFind(summaryRow[0]);
                    var graph        = new Graph(summaryRow[0]);

                    int redundentQueriesCount = 0;

                    for (int j = 0; j < summaryRow[1]; j++)
                    {
                        int[] relationship = provider.GetArray(int.Parse);
                        relationship[0]--;
                        relationship[1]--;

                        if (!graph.AddEdge(relationship[0], relationship[1]))
                        {
                            redundentQueriesCount++;
                        }
                    }

                    var components = new ConnectedComponents(graph);

                    components.Groups.Sort(new Comparison<Group>((e, a) => a.Size.CompareTo(e.Size)));

                    long total = 0;
                    long previous_value = 0;

                    foreach (var group in components.Groups)
                    {
                        foreach (var qu in group.Students)
                        {
                            int id_x = unionFind.Find(qu.X);
                            int id_y = unionFind.Find(qu.Y);
                            if (id_x != id_y)
                            {

                                int size_x = unionFind.Size(qu.X);
                                int size_y = unionFind.Size(qu.Y);

                                unionFind.Union(qu.X, qu.Y);

                                previous_value += 2 * ((long)size_x * size_y);
                                total += previous_value;
                            }
                            else
                            {
                                redundentQueriesCount++;
                            }
                        }
                    }
                    
                    Console.WriteLine(total + previous_value * redundentQueriesCount);
                }
            }
        }

        public class ConnectedComponents
        {
            private bool[] marked;
            private int[] id;
            private int count;

            public List<Group> Groups { get; set; }

            private Dictionary<int, int> verticesCount;

            public int Count
            {
                get
                {
                    return count;
                }
            }

            public int this[int vertex]
            {
                get
                {
                    return id[vertex];
                }
            }

            public int VerticesCount(int id)
            {
                if (verticesCount.ContainsKey(id)) return verticesCount[id];
                return 0;
            }

            public ConnectedComponents(Graph graph)
            {
                Groups        = new List<Group>();
                verticesCount = new Dictionary<int, int>();
                marked        = new bool[graph.VerticesCount];
                id            = new int[graph.VerticesCount];

                for (int i = 0; i < graph.VerticesCount; i++)
                {
                    if (marked[i])
                    {
                        continue;
                    }

                    verticesCount.Add(count, DepthFirstSearch(graph, i));
                    count++;
                }
            }

            /*
             * 
             */
            private int DepthFirstSearch(Graph graph, int v)
            {
                Stack<int> statck = new Stack<int>();

                statck.Push(v);
                marked[v] = true;
                id[v]     = Count;

                HashSet<Query> q = new HashSet<Query>();

                int localCount = 1;

                while (statck.Count != 0)
                {
                    v = statck.Pop();
                    foreach (var vertex in graph.Adjacent(v))
                    {
                        q.Add(new Query(v, vertex));
                        if (marked[vertex]) continue;
                        statck.Push(vertex);
                        marked[vertex] = true;
                        id[vertex] = Count;
                        localCount++;
                    }
                }

                if (q.Count != 0)
                {
                    Groups.Add(new Group { Size = localCount, Students = q });
                }

                return localCount;
            }
        }

        public class Group
        {
            public int Size { get; set; }

            public HashSet<Query> Students { get; set; }
        }

        public class Graph
        {
            private int[]          vertices;
            private HashSet<int>[] edges;

            public int VerticesCount
            {
                get
                {
                    return vertices.Length;
                }
            }

            public Graph(int verticesCount)
            {
                vertices = new int[verticesCount];
                edges    = new HashSet<int>[verticesCount];

                for (int i = 0; i < verticesCount; i++)
                {
                    edges[i] = new HashSet<int>();
                }
            }

            public Graph(Graph copy)
                : this(copy.VerticesCount)
            {
                for (int i = 0; i < copy.VerticesCount; i++)
                {
                    foreach (var v in copy.edges[i])
                    {
                        AddEdge(i, v);
                    }
                }
            }

            public bool AddEdge(int v, int w)
            {
                edges[v].Add(w);
                return edges[w].Add(v);
            }

            public void AddEdges(int v, params int[] ws)
            {
                if (ws == null) return;

                foreach (var w in ws)
                {
                    AddEdge(v, w);
                }
            }

            public void RemoveEdge(int v, int w)
            {
                edges[v].Remove(w);
                edges[w].Remove(v);
            }

            public ICollection<int> Adjacent(int v)
            {
                return edges[v];
            }
        }

        public class Query : IComparable<Query>
        {
            public int X { get; private set; }

            public int Y { get; private set; }

            public Query(int x, int y)
            {
                X = Math.Min(x, y);
                Y = Math.Max(x, y);
            }

            public override int GetHashCode()
            {
                return X << 6 ^ Y;
            }

            public override bool Equals(object obj)
            {
                return CompareTo((Query)obj) == 0;
            }

            public int CompareTo(Query other)
            {
                var cmp = X.CompareTo(other.X);
                if (cmp == 0) return Y.CompareTo(other.Y);
                return cmp;
            }

            public override string ToString()
            {
                return string.Format("{0} {1}", X + 1, Y + 1);
            }
        }

        /*
         * 
         */
        private class UnionFind
        {
            readonly int[]  parents;
            readonly int[]  rank;
            readonly int[]  size;

            public UnionFind(int items)
            {
                parents = new int[items];
                rank    = new int[items];
                size    = new int[items];

                for (int i = 0; i < items; i++)
                {
                    parents[i] = i;
                    size[i]    = 1;
                }
            }

            public int Size(int i)
            {
                return size[Find(i)];
            }

            public int Find(int i)
            {
                if (parents[i] != i)
                {
                    parents[i] = Find(parents[i]);
                }

                return parents[i];
            }

            public void Union(int id1, int id2)
            {
                int parentId1 = Find(id1);
                int parentId2 = Find(id2);

                if (parentId1 == parentId2) return;

                if (rank[parentId1] > rank[parentId2])
                {
                    parents[parentId2]  = parentId1;
                    size[parentId1]    += size[parentId2];
                }
                else
                {
                    parents[parentId1] = parentId2;
                    size[parentId2]   += size[parentId1];

                    if (rank[parentId1] == rank[parentId2])
                    {
                        rank[parentId2] += 1;
                    }
                }
            }
        }

        public interface IInputProvider
        {
            bool    IsEmpty();
            string  GetLine();
            int     GetNextInt32();
            long    GetNextInt64();
            double  GetNextDouble();
            decimal GetNextDecimal();

            T[] GetArray<T>(Func<string, T> parser);
        }

        public class InputProvider : IInputProvider, IDisposable
        {
            private StreamReader reader;
            public InputProvider()
            {

            }

            public InputProvider(string path)
            {
                if (File.Exists(path))
                    reader = new StreamReader(path);
            }

            public bool IsEmpty()
            {
                if (reader == null)
                {
                    return false;
                }

                return reader.EndOfStream;
            }

            public string GetLine()
            {
                if (reader == null)
                {
                    return Console.ReadLine();
                }

                return reader.ReadLine();
            }

            public int GetNextInt32()
            {
                return int.Parse(GetLine());
            }

            public uint GetNextUInt32()
            {
                return uint.Parse(GetLine());
            }

            public long GetNextInt64()
            {
                return long.Parse(GetLine());
            }

            public double GetNextDouble()
            {
                return double.Parse(GetLine());
            }

            public decimal GetNextDecimal()
            {
                return decimal.Parse(GetLine());
            }

            public T[] GetArray<T>(Func<string, T> parser)
            {
                string[] elements = GetLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                T[] array = new T[elements.Length];

                for (int i = 0; i < elements.Length; i++)
                {
                    array[i] = parser(elements[i]);
                }

                return array;
            }

            public void Dispose()
            {
                if (reader == null)
                {
                    return;
                }

                reader.Dispose();
            }
        }
    }
}