Cod sursa(job #2948071)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 27 noiembrie 2022 11:01:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;


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

int n, m;
vector <int> graph[200005];
vector <int> transposedGraph[200005];
bool visited[200005];
vector <int> topSort;
vector <int> ans;
vector <vector <int>> allAns;


void TopDFS(int node) {
    visited[node] = true;

    for (int newNode : graph[node]) {
        if (visited[newNode]) {
            continue;
        }
        TopDFS(newNode);
    }
    topSort.push_back(node);
}

void ReconstructionDFS(int node) {
    visited[node] = true;

    for (int newNode : transposedGraph[node]) {
        if (visited[newNode]) {
            continue;
        }
        ReconstructionDFS(newNode);
    }
    ans.push_back(node);
}

void GenerateTransposedGraph() {
    for (int i = 1; i <= n; i++) {
        for (int node : graph[i]) {
            transposedGraph[node].push_back(i);
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i ++) {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {
        if (visited[i]) {
            continue;
        }
        TopDFS(i);
    }

    // Topological Sort vec
    reverse(topSort.begin(), topSort.end());

    // Reset visited
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }

    // Generate transposed
    GenerateTransposedGraph();

    // DFS 
    for (int node : topSort) {
        if (visited[node]) {
            continue;
        }
        ReconstructionDFS(node);
        allAns.push_back(ans);

        // Reset local answer
        ans.clear();
    }

    // Answer
    fout << allAns.size() << '\n';
    for (auto vec : allAns) {
        for (auto node : vec) {
            fout << node << ' ';
        }
        fout << '\n';
    }

}