Cod sursa(job #3222700)

Utilizator MagicantPlusIuoras Andrei MagicantPlus Data 11 aprilie 2024 13:16:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;

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

vector<list<int>> graph, transGraph;
list<int> finished;
vector<bool> visitedGraph, visitedTransGraph;
list<list<int>> ctc;

int total = 0;

void dfsGraph(int node)
{
    for(auto& node_ : graph[node])
    {
        if(!visitedGraph[node_])
        {
            visitedGraph[node_] = true;
            dfsGraph(node_);
        }
    }

    finished.push_back(node);
}

void dfsTransGraph(int node)
{
    (*prev(ctc.end())).push_back(node);

    for(auto& node_ : transGraph[node])
    {
        if(!visitedTransGraph[node_])
        {
            visitedTransGraph[node_] = true;
            dfsTransGraph(node_);
        }
    }
}

int main()
{
    int n, m;

    fin >> n >> m;
    graph.resize(n + 1);
    transGraph.resize(n + 1);
    visitedGraph = vector<bool>(n + 1, false);
    visitedTransGraph = vector<bool>(n + 1, false);

    for(int i = 0; i < m; i++)
    {
        int l, r;

        fin >> l >> r;

        graph[l].push_back(r);
        transGraph[r].push_back(l);
    }

    for(int node = 1; node <= n; node++)
    {
        if(visitedGraph[node])
            continue;

        visitedGraph[node] = true;
        dfsGraph(node);
    }

    for(auto it = finished.rbegin(); it != finished.rend(); it++)
    {
        if(visitedTransGraph[*it])
            continue;

        ctc.push_back(list<int>());
        visitedTransGraph[*it] = true;
        dfsTransGraph(*it);
        total++;
    }

    fout << total << '\n';

    for(auto& e : ctc)
    {
        for(auto& node : e)
        {
            fout << node << ' ';
        }

        fout << '\n';
    }

    return 0;
}