using System;

using System.Collections.Generic;

public class Program

{

    /* Route Between Nodes: Given a directed graph, design an algorithm to find out whether there is a

    route between two nodes. */

    public class GraphNode{

        public int Val;

        public List<GraphNode> Adjacent;

        public GraphNode(int val, List<GraphNode> list = null){

            this.Val = val;

            this.Adjacent = list==null ? new List<GraphNode>() : list;

        }

    }

    public static bool RouteBetweenNodes(GraphNode source, GraphNode target){

        var queue = new Queue<GraphNode>();

        queue.Enqueue(source);

        return RouteBetweenNodes(target, queue, new HashSet<GraphNode>());

    }

    private static bool RouteBetweenNodes(GraphNode nodeToFind, Queue<GraphNode> toVisit, HashSet<GraphNode> visited){

        while (toVisit.Count != 0){

            var curr = toVisit.Dequeue();

            if (visited.Contains(curr)) continue;

            if (curr == nodeToFind) return true;

            visited.Add(curr);

            foreach(var vertex in curr.Adjacent){

                toVisit.Enqueue(vertex);

            }

        }

        return false;

    }

    public static void Main()

    {

        var node8 = new GraphNode(8);

        var node6 = new GraphNode(6, new List<GraphNode>(){node8});

        var node0 = new GraphNode(0);

        var node9 = new GraphNode(9);

        var node1 = new GraphNode(1, new List<GraphNode>(){node0, node6, node9});

        var node7 = new GraphNode(7);

        var node2 = new GraphNode(2, new List<GraphNode>(){node7});

        var node10 = new GraphNode(10, new List<GraphNode>(){node2, node1});

        Console.WriteLine(RouteBetweenNodes(node10, node0));//T

        Console.WriteLine(RouteBetweenNodes(node2, node7));//T

        Console.WriteLine(RouteBetweenNodes(node2, node8));//F

        Console.WriteLine(RouteBetweenNodes(node1, node8));//T

        Console.WriteLine(RouteBetweenNodes(node1, node7));//F

    }

}