21. Problems on Graph - II

 

import java.util.ArrayList;

import java.util.Stack;

class Graph{

   

    @SuppressWarnings("unchecked")

    void connectedComponents(ArrayList<Edge> graph[]) {

        ArrayList<Edge> transposedGraph[] = new ArrayList[graph.length];

        for (int i = 0; i < graph.length; i++)

            transposedGraph[i] = new ArrayList<Edge>();

        boolean visited[] = new boolean[graph.length];

        Stack<Integer> stack = topologicalSort(graph);

        for (int i = 0; i < graph.length; i++)

            for (Edge edge : graph[i])

                transposedGraph[edge.dest].add(new Edge(edge.dest, edge.src));

        while (!stack.empty()) {

            int root = stack.pop();

            if (!visited[root]) {

                depthFirstTraversal(transposedGraph, root, visited);

                System.out.println();

            }

        }

    }

    private void tarjanAlgo(ArrayList<Edge> graph[], int root, boolean visited[], int dt[], int ldt[], int time,

            int parent) {

        visited[root] = true;

        dt[root] = ldt[root] = ++time;

        for (Edge edge : graph[root]) {

            if (edge.dest == parent)

                continue;

            else if (!visited[edge.dest]) {

                tarjanAlgo(graph, edge.dest, visited, dt, ldt, time, root);

                ldt[root] = Math.min(ldt[root], ldt[edge.dest]);

                if (dt[root] < ldt[edge.dest])

                    System.out.println("Bridge: " + root + " --> " + edge.dest);

            } else if (visited[edge.dest])

                ldt[root] = Math.min(ldt[root], dt[edge.dest]);

        }

    }

    void getBridge(ArrayList<Edge> graph[]) {

        int dt[] = new int[graph.length];

        int ldt[] = new int[graph.length];

        boolean visited[] = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++) {

            if (!visited[i]) {

                tarjanAlgo(graph, i, visited, dt, ldt, 0, -1);

            }

        }

    }

    private void tarjanAlgoAP(ArrayList<Edge> graph[], int root, int parent, int dt[], int ldt[], boolean visited[],

            int time, boolean ap[]) {

        visited[root] = true;

        dt[root] = ldt[root] = ++time;

        int children = 0;

        for (Edge edge : graph[root]) {

            if (parent == edge.dest)

                continue;

            else if (visited[edge.dest])

                ldt[root] = Math.min(ldt[root], dt[edge.dest]);

            else{

                tarjanAlgoAP(graph, edge.dest, root, dt, ldt, visited, time, ap);

                if(dt[root] <= ldt[edge.dest] && parent != -1)

                ap[root] = true;

                children++;

            }

        }

        if(parent == -1 && children > 1)

        ap[root] = true;

    }

    void getAP(ArrayList<Edge> graph[]) {

        int dt[] = new int[graph.length];

        int ldt[] = new int[graph.length];

        boolean visited[] = new boolean[graph.length];

        boolean ap[] = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++)

            if (!visited[i])

                tarjanAlgoAP(graph, i, -1, dt, ldt, visited, 0, ap);

       

        for(int i = 0; i < ap.length; i++)

        if(ap[i])

        System.out.print(i+" ");

    }

}