Cod sursa(job #2850664)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 17 februarie 2022 12:00:20
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, M;
vector<vector<int>> edges;
vector<vector<int>> inverse_edges;
vector<int> topo;
vector<bool> visited;
vector<vector<int>> scc;

void dfs(int node0) {
    visited[node0] = 1;

    for(auto node: edges[node0]) {
        if(!visited[node]) {
            dfs(node);
        }
    }

    topo.push_back(node0);
}

void inverse_dfs(int node0) {
    visited[node0] = 1;
    scc.back().push_back(node0);

    for(auto node: inverse_edges[node0]) {
        if(!visited[node]) {
           inverse_dfs(node);
        }
    }
}

int main() {
    fin >> N >> M;

    edges = vector<vector<int>> (N + 1);
    inverse_edges = vector<vector<int>> (N + 1);

    for(int i = 1; i <= M; i++) {
        int x, y;
        fin >> x >> y;

        edges[x].push_back(y);
        inverse_edges[y].push_back(x);
    }

    visited = vector<bool> (N + 1, 0);

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

    visited = vector<bool> (N + 1, 0);

    for(int i = (int) topo.size() - 1; i >= 0; i--) {
        scc.push_back({});
        if(!visited[topo[i]]) {
            inverse_dfs(topo[i]);
        }

        if(scc.back().size() == 0) {
            scc.pop_back();
        }
    }

    fout << scc.size() << '\n';

    for(int i = 0; i < (int) scc.size(); i++) {
        for(int j = 0; j < (int) scc[i].size(); j++) {
            fout << scc[i][j] << " ";
        }
        fout << '\n';
    }

    return 0;
}