Cod sursa(job #2928893)

Utilizator cilteaioanaIoana C cilteaioana Data 24 octombrie 2022 02:37:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>

using namespace std;

int n, m;
vector <vector <int>> la, transp;
vector <bool> vis;
vector <int> topo;
vector <vector <int>> res;
vector <int> aux;

void dfs1(int node) 
{
    vis[node] = true;
    for (auto& x : la[node]) 
        if (!vis[x]) 
            dfs1(x);
    topo.push_back(node);
}

void dfs2(int node) 
{
    aux.push_back(node);
    vis[node] = true;
    for (auto& x : transp[node]) 
        if (!vis[x]) 
            dfs2(x);
}

int main() 
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> n >> m;
    
    transp = la = vector<vector<int>>(n, vector<int>());
    vis = vector<bool>(n, false);
    for (int i = 0; i < m; ++i) 
    {
        int x, y;
        fin >> x >> y;
        --x; --y;
        la[x].push_back(y);
        transp[y].push_back(x);
    }

    fin.close();

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            dfs1(i);
        }
    }
    vis = vector <bool>(n, false);
    for (int i = n - 1; i >= 0; --i) {
        if (!vis[topo[i]]) {
            aux.clear();
            dfs2(topo[i]);
            res.push_back(aux);
        }
    }
    fout << res.size() << "\n";

    for (auto& v : res) {
        for (auto& i : v) {
            fout << i + 1 << " ";
        }
        fout << "\n";
    }
    fout.close();
    return 0;
}