using System;

using System.Collections.Generic;

public class Program {

    public static void Main()   {

        var graph = new DirectedGraph(13);

        PopulateGraph(graph);

        var scc = new StronglyConnectedComponents(graph);    

        Console.WriteLine(scc.AreStronglyConnected(2, 5));

    }

    public static void PopulateGraph(DirectedGraph graph) {

        graph.AddEdge(4, 2);

        graph.AddEdge(2, 3);

        graph.AddEdge(3, 2);

        graph.AddEdge(6, 0);

        graph.AddEdge(0, 1);

        graph.AddEdge(2, 0);

        graph.AddEdge(11, 12);

        graph.AddEdge(12, 9);

        graph.AddEdge(9, 10);

        graph.AddEdge(9, 11);

        graph.AddEdge(7, 9);

        graph.AddEdge(10, 12);

        graph.AddEdge(11, 4);

        graph.AddEdge(4, 3);

        graph.AddEdge(3, 5);

        graph.AddEdge(6, 8);

        graph.AddEdge(8, 6);

        graph.AddEdge(5, 4);

        graph.AddEdge(0, 5);

        graph.AddEdge(6, 4);

        graph.AddEdge(6, 9);

        graph.AddEdge(7, 6);        

    }

}

​

public class StronglyConnectedComponents {

    private bool[] visited;

    private int[] componentIds;

    public int ComponentCount { get; private set; } 

​

    public StronglyConnectedComponents(DirectedGraph graph) {

        visited = new bool[graph.VertexCount];

        componentIds = new int[graph.VertexCount];

        var order = new GraphTraversal(graph).ReverseOrder();

        var reversedGraph = graph.Reverse();

        foreach (var vertex in order) {

            if (!visited[vertex]) {

                DepthFirstSearch(reversedGraph, vertex);

                ComponentCount++;

            }

        }

    }

    public int VertexComponentId(int vertex) {

        return componentIds[vertex];

    }

    public bool AreStronglyConnected(int source, int target) {

        return componentIds[source] == componentIds[target];

    }     

    private void DepthFirstSearch(DirectedGraph graph, int vertex) {

        visited[vertex] = true;

        componentIds[vertex] = ComponentCount;

        foreach (var adjacent in graph.AdjacentTo(vertex)) {

            if (!visited[adjacent]) {

                DepthFirstSearch(graph, adjacent);

            }

        }

    }                 

}

​

public class GraphTraversal {

    private Stack<int> reversePostOrder;

    private bool[] visited;

    public GraphTraversal(DirectedGraph graph) {

        visited = new bool[graph.VertexCount];

        reversePostOrder = new Stack<int>();

        for (var vertex = 0; vertex < graph.VertexCount; vertex++) {

            if (!visited[vertex]) {

                DepthFirstSearch(graph, vertex);

            }

        }

    }

    public IEnumerable<int> ReverseOrder() {

        return reversePostOrder;

    }

    private void DepthFirstSearch(DirectedGraph graph, int vertex) {

        visited[vertex] = true;

        foreach (var adjacent in graph.AdjacentTo(vertex)) {

            if (!visited[adjacent]) {

                DepthFirstSearch(graph, adjacent);

            }

        }

        reversePostOrder.Push(vertex);

    }

}

​

public class DirectedGraph {

    public int VertexCount { get; set; }

    public int EdgeCount { get; set; }

    private List<int>[] adjacencyLists;

    public DirectedGraph(int vertexCount) {

        VertexCount = vertexCount;

        EdgeCount = 0;

        InitializeAdjacencyLists(vertexCount);

    }   

    public void AddEdge(int from, int to) {

        adjacencyLists[from].Add(to);

        EdgeCount++;

    }

    public IEnumerable<int> AdjacentTo(int vertex) {

        return adjacencyLists[vertex];

    }    

    public DirectedGraph Reverse() {

        var reversedGraph = new DirectedGraph(this.VertexCount);

        for (var vertex = 0; vertex < this.VertexCount; vertex++) {

            foreach (var adjacent in this.AdjacentTo(vertex)) {

                reversedGraph.AddEdge(adjacent, vertex);

            }

        }

        return reversedGraph;

    }

    public override string ToString() {

        String graghString = VertexCount + " vertices, " + EdgeCount + " edges \n";        

        for (int vertex = 0; vertex < VertexCount; vertex++) {

            graghString+= vertex + ": ";           

            foreach (var adjacnet in this.AdjacentTo(vertex)) {

                graghString += adjacnet + " ";

            }

            graghString += "\n";        

        }

        return graghString;

    }      

    private void InitializeAdjacencyLists(int vertexCount) {

        adjacencyLists = new List<int>[vertexCount];

        for (var vertex = 0; vertex < vertexCount; vertex++) {

            adjacencyLists[vertex] = new List<int>();

        }

    }

}