#include <iostream>
#include <vector>
#include <stack>

typedef int                             Node;
typedef std::vector<std::vector<Node>>  List;

void dfs(List& neighbours, 
         std::stack<Node>& s, 
         std::vector<bool>& visited, 
         bool transposed, 
         Node u)
{
    visited[u] = true;

    for (Node v : neighbours[u]) {
        if (!visited[v]) {
            dfs(neighbours, s, visited, transposed, v);
        }
    }
    
    if (transposed) {
        std::cout << u << " ";
    } else {
        s.push(u);
    }
}


List transpose(List& neighbours)
{
    const int n = neighbours.size();

    List new_neighbours(n);

    for (Node u = 0; u < n; u++) {
        for (Node v : neighbours[u]) {
            new_neighbours[v].push_back(u);
        }
    }
        
    return new_neighbours;
}

void scc(List& neighbours)
{
    const int n = neighbours.size();

    std::vector<bool> visited(n, false);
    std::stack<int> s;

    // DFS(G)
    for (int u = 0; u < n; u++) {
        if (!visited[u]) {
            dfs(neighbours, s, visited, false, u);
        }
    }
    
    // G^T
    List neighbours_T = transpose(neighbours);

    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }

    // DFS(G^T) po opadajucem radu u.f
    int k = 0;
    while (!s.empty()) {
        Node u = s.top(); s.pop();
        if (!visited[u]) {
            std::cout << "Komponenta #" << ++k << ": ";
            dfs(neighbours_T, s, visited, true, u);
            std::cout << std::endl;
        }
    }
}


int main(int argc, const char *argv[])
{
    List neighbours = {
        {1},
        {2, 4, 5},
        {3, 6},
        {2, 7},
        {0, 5},
        {6},
        {5, 7},
        {7}
    };

    scc(neighbours);
    
    return 0;
}