Strongly component

Question

I am trying to write an algorithm that is given a graph G and 2 nodes 'x' and 'y'as input, which returns whether there is a cyclic path from 'x' to 'y'

Is it a good idea to find the strongly connected components first and then check if x and y belong to same strongly connected component.
If they belong to different connected component say x belongs to C1 and y belongs to C2, then if there exists a path from C1 to C2, then we can say that there is a cyclic path from x to y.

Answer 1

Your idea with strongly connected components should work. Here is a graph and some code for you to experiment:

First, a digraph:

And it's adjacency lists representation:

13 vertices, 22 edges
0: 5 1
1: 
2: 0 3
3: 5 2
4: 3 2
5: 4
6: 9 4 8 0
7: 6 9
8: 6
9: 11 10
10: 12
11: 4 12
12: 9

And it's strongly connected components:

7
6 8
9 10 11 12
0 2 3 4 5
1

Now, after with implementation for digraph and Kosaraju-Sharir

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);
            }
        }
    }
}

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);
    }
}

class DirectedGraph
{
    public int VertexCount { get; set; }
    public int EdgeCount { get; set; } = 0;

    private List<int>[] adjacencyLists;

    public DirectedGraph(int vertexCount)
    {
        VertexCount = vertexCount;
        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>();
        }
    }
}

Queries like scc.AreStronglyConnected(2, 5) will tell if directed cycle between vertices exists. Runnable code is here.