// C program to implement tarjan's algorithm

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// Maximum number of vertices in the graph
#define MAX 100

// Structure to represent a graph
struct Graph {
    // Number of vertices
    int V;
    // Adjacency matrix representation of the graph
    int adj[MAX][MAX];
};

// Function to create a graph with V vertices
struct Graph* createGraph(int V)
{
    // Allocate memory for the graph
    struct Graph* graph
        = (struct Graph*)malloc(sizeof(struct Graph));
    // Set the number of vertices
    graph->V = V;
    // Initialize the adjacency matrix to 0
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            graph->adj[i][j] = 0;
    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int u, int v)
{
    // Set the edge from u to v
    graph->adj[u][v] = 1;
}

int disc[MAX], low[MAX], stackMember[MAX], stack[MAX];
int time = 0, top = -1;

// A utility function to find the SCCs using DFS
void SCCUtil(struct Graph* graph, int u)
{
    // Initialize discovery and low values
    static int time = 0;
    disc[u] = low[u] = ++time;
    // Push the vertex onto the stack
    stack[++top] = u;
    stackMember[u] = 1;

    // Go through all vertices adjacent to this vertex
    for (int v = 0; v < graph->V; v++) {
        // If v is not visited yet, recur for it
        if (graph->adj[u][v]) {
            if (disc[v] == -1) {
                SCCUtil(graph, v);
                // Check if the subtree rooted at v has a
                // connection back to one of the ancestors
                // of u
                low[u]
                    = (low[u] < low[v]) ? low[u] : low[v];
            }
            // Update low value of u for parent function
            // calls
            else if (stackMember[v]) {
                low[u]
                    = (low[u] < disc[v]) ? low[u] : disc[v];
            }
        }
    }
    // To store stack extracted vertices
    int w = 0;
    // If u is a root node, pop all vertices from the stack
    // and print them
    if (low[u] == disc[u]) {
        while (stack[top] != u) {
            w = stack[top--];
            printf("%d ", w);
            stackMember[w] = 0;
        }
        w = stack[top--];
        printf("%d\n", w);
        stackMember[w] = 0;
    }
}

// Function to find and print all SCCs
void SCC(struct Graph* graph)
{
    // Initialize discovery and low values to -1
    for (int i = 0; i < graph->V; i++) {
        disc[i] = -1;
        low[i] = -1;
        stackMember[i] = 0;
    }

    // Call the recursive helper function to find SCCs in
    // DFS tree rooted with vertex i
    for (int i = 0; i < graph->V; i++) {
        if (disc[i] == -1) {
            SCCUtil(graph, i);
        }
    }
}

int main()
{
    // Create a graph with 5 vertices
    struct Graph* graph = createGraph(5);
    // Add edges to the graph
    addEdge(graph, 1, 0);
    addEdge(graph, 0, 2);
    addEdge(graph, 2, 1);
    addEdge(graph, 0, 3);
    addEdge(graph, 3, 4);

    // Print the SCCs
    printf("Strongly Connected Components in the given "
           "graph:\n");
    SCC(graph);

    return 0;
}