Java Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph

Code:

package com.executecodes.graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class StronglyorWeaklyConnectedDigraphs
{
    private int                 V;
    private int                 preCount;
    private int[]               low;
    private boolean[]           visited;
    private List[]     graph;
    private List> sccComp;
    private Stack      stack;

    /** function to get all strongly connected components **/
    public List> getSCComponents(List[] graph)
    {
        V = graph.length;
        this.graph = graph;
        low = new int[V];
        visited = new boolean[V];
        stack = new Stack();
        sccComp = new ArrayList<>();
        for (int v = 0; v < V; v++)
            if (!visited[v])
                dfs(v);
        return sccComp;
    }

    /** function dfs **/
    public void dfs(int v)
    {
        low[v] = preCount++;
        visited[v] = true;
        stack.push(v);
        int min = low[v];
        for (int w : graph[v])
        {
            if (!visited[w])
                dfs(w);
            if (low[w] < min)
                min = low[w];
        }
        if (min < low[v])
        {
            low[v] = min;
            return;
        }
        List component = new ArrayList();
        int w;
        do
        {
            w = stack.pop();
            component.add(w);
            low[w] = V;
        }
        while (w != v);
        sccComp.add(component);
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter number of Vertices");
        /** number of vertices **/
        int V = scan.nextInt();
        /** make graph **/
        List[] g = new List[V];
        for (int i = 0; i < V; i++)
            g[i] = new ArrayList();
        /** accept all edges **/
        System.out.println("Enter number of edges");
        int E = scan.nextInt();
        /** all edges **/
        System.out.println("Enter the edges in the graph : ");
        for (int i = 0; i < E; i++)
        {
            int x = scan.nextInt();
            int y = scan.nextInt();
            g[x].add(y);
        }
        StronglyConnectedGraph t = new StronglyConnectedGraph();
        System.out.print("The graph is : ");
        /** print all strongly connected components **/
        List> scComponents = t.getSCComponents(g);
        Iterator> iterator = scComponents.iterator();
        boolean weaklyConnected = false;
        while (iterator.hasNext())
        {
            if (iterator.next().size() <= 1)
            {
                weaklyConnected = true;
            }
        }
        if (weaklyConnected == true)
            System.out.println("Weakly Connected");
        else
            System.out.println("Strongly Connected");
        scan.close();
    }
}


Output:

Enter number of Vertices

6
Enter number of edges
7
Enter the edges in the graph :
0 1
1 2
1 3
3 4
4 5
5 3
5 2
The graph is : Weakly Connected



More Java Programs: