using System;

using System.Collections.Generic;

/*

Given an unweighted, undirected graph which represents a metro map as follows

     1 - 2

   / |   |

  3  4   5

  |  | /

  6- 7 

  Input: graph = [[1,2],[1,4][1,3],[2,5],[3,6],[4,7],[6,7],[5,7]], start = 1, end = 6

  Output: 2

     1 - 2

   / |   |

  3  4   5

  |  | /

  6- 7 - 8 

  Input: graph = [[1,2],[1,4][1,3],[2,5],[3,6],[4,7],[6,7],[5,7],[7,8]], start = 1, end = 8

  Output: 3 

vertices are stations

edges are the path between two stations

Given a start station and ending station, determine the minimum number of stops that must be made to get to the destination.

​

Input: A Graph (unweighted/undirected), a starting Vertex, and an ending Vertex

Output: Integer

​

Question: Can there be cycles? if yes, need to track parent

​

stations [0,1,2,3,4,...]

start: 1

end: 4

output: min number of stops

Approach:

  - Use DFS to explore all edges (connections) of vertices (stations)

  - Take minimum of distance of all paths

Steps:

  - Create a dictionary to hold all nodes edges

     - foreach connection in graph

       - create map for both start and end nodes

       - add to list of edges if node exists

  - Create a visited hash to keep track of visited stations    

  - Create helper getMinStops

  - minDistance = helper(map, start, end, visited, 0

getMinStops(dictionary map, i, end, visited, distance)

   - base cases

     if i == end  <-- goal state

        return distance

​

   - recurse cases     

     visited.Add(i)

     minDistance = int.Max

     edges = map[i]

     explore edges

     foreach edge in edges

        if (!visited)

            minDistance = min(minDistance, getMinStops(map, edge, end, visited, distance + 1) 

        else (if cycles allowed)

           if (edge != origin

              return int.Max

     return minDistance

*/

public class Program

{

    public static void Main()

    {

        List<Tuple<List<int[]>,int,int>> tests = new List<Tuple<List<int[]>,int,int>>();

        tests.Add(new Tuple<List<int[]>,int,int>( new List<int[]>(){

                                    new int[2]{1,2},

                                    new int[2]{1,4},

                                    new int[2]{1,3},

                                    new int[2]{2,5},

                                    new int[2]{3,6},

                                    new int[2]{4,7},

                                    new int[2]{6,7},

                                    new int[2]{5,7}}, 1, 6));

        tests.Add(new Tuple<List<int[]>,int,int>( new List<int[]>(){

                                    new int[2]{1,2},

                                    new int[2]{1,4},

                                    new int[2]{1,3},

                                    new int[2]{2,5},

                                    new int[2]{3,6},

                                    new int[2]{4,7},

                                    new int[2]{6,7},

                                    new int[2]{5,7},

                                    new int[2]{7,8}}, 1, 8));       

        foreach(var test in tests)

        {

            int result = GetMinNoStops(test.Item1, test.Item2, test.Item3);

            Console.WriteLine("--------> Minimum number of stops from {0} to {1} is: {2} <-------",test.Item2,test.Item3, result);

        }

    }

    public static int GetMinNoStops(List<int[]> graph, int start, int end)

    {

        // create dictionary map

        Dictionary<int,List<int>> map = new Dictionary<int,List<int>>();

        HashSet<int> visited = new HashSet<int>();

        foreach(var pair in graph)

        {

            if (!map.ContainsKey(pair[0]))

                map.Add(pair[0], new List<int>(){pair[1]});

            else

                map[pair[0]].Add(pair[1]);

            if (!map.ContainsKey(pair[1]))

                map.Add(pair[1], new List<int>(){pair[0]});

            else

                map[pair[1]].Add(pair[0]);          

        }

        foreach(var pair in map)

        {

            Console.WriteLine("[{0}|{1}]", pair.Key, string.Join(",", pair.Value));

        }

        return minStops(map, start, end, visited, 0);

    }

    private static int minStops(Dictionary<int,List<int>> map, int i, int end, HashSet<int> visited, int distance)

    {

        // base case

        if (i == end) // goal state

            return distance;

        // recurse cases

        visited.Add(i);

        int minDistance = Int32.MaxValue;

        List<int> edges = map[i];

        //Console.WriteLine("exploring: {0} to {1}", i, end);

        foreach(var node in edges)

        {

            if (!visited.Contains(node))

            {

                int currDistance = minStops(map, node, end, visited, distance + 1);

                minDistance = Math.Min(minDistance, currDistance);

            }

        }

        visited.Remove(i);

        return minDistance;

    }

}