Cod sursa(job #2663126)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 25 octombrie 2020 13:47:29
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>

constexpr auto max_n = 100005;

using namespace std;

vector<int> graph[max_n];
vector<int> transposed_graph[max_n];
int visited[max_n];
int node_order[max_n];
int node_order_count = 0;
vector<int> components[max_n];
int component_count = 0;

void dfs1(const int node)
{
    visited[node] = 1;
    for (auto neighbor : graph[node])
        if (!visited[neighbor])
            dfs1(neighbor);

    node_order[node_order_count++] = node;
}

void dfs2(const int node)
{
    visited[node] = 2;

    components[component_count].push_back(node);
    
    for (auto neighbor : transposed_graph[node])
        if (visited[neighbor] != 2)
            dfs2(neighbor);
}

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int n, m;
    fin >> n >> m;

    for (auto i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;

        graph[x].push_back(y);
        transposed_graph[y].push_back(x);
    }

    fin.close();

    for (auto i = 1; i <= n; i++)
        if (!visited[i])
            dfs1(i);
    
    for (auto i = node_order_count - 1; i >= 0; i--)
    {
        const auto node = node_order[i];

        if (visited[node] != 2)
        {
            dfs2(node);
            component_count++;
        }
    }

    fout << component_count << endl;
    for (auto i = 0; i < component_count; i++)
    {
        for (auto node : components[i])
            fout << node << " ";
        fout << endl;
    }

    fout.close();
    return 0;
}