Cod sursa(job #2924633)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 6 octombrie 2022 21:01:30
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e5;

int n;
int m;
vector<vector<int>> graph;
vector<vector<int>> graphTranspose;
vector<bool> visited;
vector<int> postOrder;
vector<vector<int>> ctc;

void read() {
    cin >> n >> m;
    graph.resize(n + 1);
    graphTranspose.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graphTranspose[b].push_back(a);
    }
}

void dfs(int node) {
    visited[node] = true;
    for (int neighbour: graph[node])
        if (!visited[neighbour])
            dfs(neighbour);
    postOrder.push_back(node);
}

void dfsTranspose(int node) {
    visited[node] = false;
    ctc.back().push_back(node);
    for (int neighbour: graphTranspose[node])
        if (visited[neighbour])
            dfsTranspose(neighbour);
}

void computeCtc() {
    vector<int> postOrder;
    visited.resize(n + 1);

    for (int i = 1; i <= n; i++)
        if (!visited[i])
            dfs(i);

    for (int i = 1; i <= n; i++)
        if (visited[i]) {
            ctc.push_back(vector<int>());
            dfsTranspose(i);
        }
}

void print() {
    cout << ctc.size() << endl;
    for (vector<int> component: ctc) {
        for (int node: component)
            cout << node << " ";
        cout << endl;
    }
}

int main() {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    read();
    computeCtc();
    print();

    return 0;
}