Untitled

#include <functional>
#include <utility>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <unordered_set>


class Graph {
public:

    using graph_type = std::vector<std::unordered_set<int> >;

    Graph() = default;
    Graph(int num_vertices) {
        g.resize(num_vertices);
    }
    Graph(const graph_type& g) : g(g) {};
    Graph(graph_type&& g) : g(std::move(g)) {};

    void AddEgde(int from, int to) {
        g[from].insert(to);
    }

    int NumVertices() const {
        return g.size();
    }
    
    const std::unordered_set<int>& GetNeighbours(int v) const{
        return g[v];
    }

    ~Graph() = default;

private:
    graph_type g;
};

enum class Color {
    WHITE = 0,
    GRAY = 1,
    BLACK = 2
};

// bool HasCycle(const Graph& g, int v, std::vector<Color>& visited) {
//     visited[v] = Color::GRAY;

//     for (const auto& child: g.GetNeighbours(v)) {
//         if (visited[child] == Color::WHITE) {
//             HasCycle(g, child, visited);
//         }
//         if (visited[child] == Color::GRAY) {
//             return true;
//         }
//     }

//     visited[v] = Color::BLACK;
//     return false;
// }


// bool HasCycle(const Graph& g) {
//     size_t num_vertices = g.NumVertices();

//     std::vector<Color> visited(num_vertices, Color::WHITE);
//     for (int i = 0; i < num_vertices; ++i) {
//         if (visited[i] == Color::WHITE) {
//             if (HasCycle(g, i, visited)) {
//                 return true;
//             }
//         }
//     }
//     return false;
// }

// void DFS(const Graph& g, int v, std::vector<Color>& visited, std::vector<int>& sorted) {
//     visited[v] = Color::GRAY;

//     for (const auto& child: g.GetNeighbours(v)) {
//         if (visited[child] == Color::WHITE) {
//             DFS(g, child, visited, sorted);
//         }
//     }

//     sorted.push_back(v);
//     visited[v] = Color::BLACK;
// }


// std::vector<int> TopologicalSort(const Graph& g) {
//     if (HasCycle(g)) {
//         throw std::string("graph has cycle!");
//     }

//     size_t num_vertices = g.NumVertices();
//     std::vector<int> sorted;
//     sorted.reserve(num_vertices);
    
//     std::vector<Color> visited(num_vertices, Color::WHITE);
//     for (int i = 0; i < num_vertices; ++i) {
//         if (visited[i] == Color::WHITE) {
//             DFS(g, i, visited, sorted);
//         }
//     }
//     std::reverse(sorted.begin(), sorted.end());

//     return sorted;
// }


void DFS(const Graph& g, int v, std::vector<Color>& visited, std::vector<int>& time_out) {
    visited[v] = Color::GRAY;

    for (const auto& child: g.GetNeighbours(v)) {
        if (visited[child] == Color::WHITE) {
            DFS(g, child, visited, time_out);
        }
    }

    visited[v] = Color::BLACK;
    time_out.push_back(v);
}


std::vector<int> DFS(const Graph& g) {
    size_t num_vertices = g.NumVertices();
    std::vector<int> time_out;
    time_out.reserve(num_vertices);
    
    std::vector<Color> visited(num_vertices, Color::WHITE);
    for (int i = 0; i < num_vertices; ++i) {
        if (visited[i] == Color::WHITE) {
            DFS(g, i, visited, time_out);
        }
    }

    std::reverse(time_out.begin(), time_out.end());
    return time_out;
}

Graph BuildInverted(const Graph& g) {
    size_t num_vertices = g.NumVertices();
    Graph inverted(num_vertices);
    for (int i = 0; i < num_vertices; ++i) {
        for (const auto& v: g.GetNeighbours(i)) {
            inverted.AddEgde(v, i);
        }
    }
    return inverted;
}

void TraverseSCC(const Graph& g, 
                 int v, std::vector<Color>& visited, 
                 std::unordered_map<int, int>& SCC_indices,
                 int strong_comp_num) {
    visited[v] = Color::GRAY;

    SCC_indices[v] = strong_comp_num;

    for (const auto& child: g.GetNeighbours(v)) {
        if (visited[child] == Color::WHITE) {
            TraverseSCC(g, child, visited, SCC_indices, strong_comp_num);
        }
    }

    visited[v] = Color::BLACK;
}

std::pair<std::unordered_map<int, int>, int> FindSCC(const Graph& g) {
    size_t num_vertices = g.NumVertices();
    std::unordered_map<int, int> SCC_index(num_vertices);

    std::vector<int> time_out = DFS(g);
    std::vector<Color> visited(num_vertices, Color::WHITE);

    Graph inverted = BuildInverted(g);

    int strong_comp_num = 0;
    for (const auto& v: time_out) {
        if (visited[v] == Color::WHITE) {
            TraverseSCC(inverted, v, visited, SCC_index, strong_comp_num);
            ++strong_comp_num;
        }
    }
    
    return std::make_pair(SCC_index, strong_comp_num);
}

Graph GraphCondensation(const Graph& g) {
    size_t num_vertices = g.NumVertices();

    const auto& [SCC_index, strong_comp_num] = FindSCC(g);

    Graph condensed_graph(strong_comp_num);

    for (int from = 0; from < num_vertices; ++from) {
        for (const auto& to: g.GetNeighbours(from)) {
            if (SCC_index.at(to) != SCC_index.at(from)) {
                condensed_graph.AddEgde(SCC_index.at(from), SCC_index.at(to));
            }
        }
    }

    return condensed_graph;

}


/*
7
9
0 1
1 3
2 0
3 2
3 4
1 4
4 5
5 6
6 4
*/


int main() {

    int n;
    std::cin >> n;

    int m;
    std::cin >> m;

    Graph g(n);

    for (int i = 0; i < m; ++i) {
        int from, to;
        std::cin >> from >> to;

        g.AddEgde(from, to);
    }

    const auto& [SCC_index, strong_comp_num] = FindSCC(g);

    std::cout << strong_comp_num << std::endl;
    for (const auto& [v, idx]: SCC_index) {
        std::cout << "v: " << v << " idx: " << idx << std::endl;
    }

    auto condensed_graph = GraphCondensation(g);

    for (int from = 0; from < condensed_graph.NumVertices(); ++from) {
        std::cout << "from: " << from <<"   to:";
        for (const auto& to: condensed_graph.GetNeighbours(from)) {
            std::cout << to <<" ";
        }
        std::cout << std::endl;
    }

    return 0;
}