#codingexercise
Given a list of data centers and their connectivity information, find the islands of isolated data centers,

e.g. Input A<->B, B<->C, D<->E // Edges

Output : {A,B,C}, {D,E}

A, B, C , D, E

We create an Adjacency List with the given Edges List and Vertices List

A - B

B - A, C

C - B

D - E

E-  D

List<List<Node>> GetIslands(List<Tuple<Node, Node>> pairs, List<Node> vertices)

        {

            var ret = new List<List<Node>>();

            var t = GetAdjacencyList(pairs, vertices);

           

            foreach (var vertex in vertices)

            {

                 var connected = BFS(t, vertex);

                 bool merge = false;

                 for (int i =0;i < ret.Count; i++)

                 {

                    var path = ret[i];

                     if (path.Intersect(connected).ToList().Count > 0){

                     var g = path.Union(connected).ToList<Node>();

                         ret[i] = g.Distinct<Node>().ToList<Node>();

                         merge = true;

                         break;

                     }                     

                 }

                if (merge == false)

                    ret.Add(connected);

            }

           

            return ret;

        }

Hashtable<Node, List<Node>> GetAdjacencyList(List<Tuple<Node, Node>> pairs, List<Node> vertices)

        {

            // build an adjacency list from the edges
            // initialize a list for every vertex
            var t = new Dictionary<Node, List<Node>>();
            foreach (var p in pairs)
            {
                //forward
                if (t.Keys.Contains(p.Item1))
                {
                    t[p.Item1].Add(p.Item2);
                }
                else
                {
                    t.Add(p.Item1, new List<Node>{p.Item2});
                }
                //backward
                if (t.Keys.Contains(p.Item2))
                {
                    t[p.Item2].Add(p.Item1);
                }
                else
                {
                    t.Add(p.Item2, new List<Node>{p.Item1});
                }  
            }
            // Add empty list for every vertex
            var remaining = vertices.Except(t.Keys).ToList();
             foreach (var v in remaining)
                      t.Add(v, new List<Node>());
            return t;

        }

List<Node> BFS(AdjacencyList h, Node root)

{

    var ret = new List<Node>();

    if (root == null) return ret;

    var q = new Queue();

    q.Enqueue(root);

    var current = q.Dequeue();

    while(current)

    {

        foreach(var v in h[current])

        {

            if (ret.Contains(v) == false && v != root){

                ret.Add(v);

                q.Enqueue(v);

            }

        }

        current = q.Dequeue();

    }

    return ret;

}
We can also make some optimizations in the main loop by breaking early when all the vertices are covered.