Cod sursa(job #2924540)

Utilizator trifangrobertRobert Trifan trifangrobert Data 4 octombrie 2022 19:46:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>

using namespace std;

int N, M;
vector <vector <int>> graph, rev_graph;
vector <bool> seen;
vector <int> topo;
vector <vector <int>> answer;
vector <int> aux;

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

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

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> N >> M;
    graph = vector<vector<int>>(N, vector<int>());
    rev_graph = vector<vector<int>>(N, vector<int>());
    seen = vector<bool>(N, false);
    for (int i = 0; i < M; ++i) {
        int u, v;
        fin >> u >> v;
        --u; --v;
        graph[u].push_back(v);
        rev_graph[v].push_back(u);
    }
    for (int i = 0; i < N; ++i) {
        if (!seen[i]) {
            dfs1(i);
        }
    }
    seen = vector <bool>(N, false);
    for (int i = N - 1; i >= 0; --i) {
        if (!seen[topo[i]]) {
            aux.clear();
            dfs2(topo[i]);
            answer.push_back(aux);
        }
    }
    fout << answer.size() << "\n";
    for (auto& v : answer) {
        for (auto& i : v) {
            fout << i + 1 << " ";
        }
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}