Cod sursa(job #3271035)

Utilizator error500Ursaru Tudor Alexandru error500 Data 25 ianuarie 2025 09:01:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <string.h>

#include <fstream>
#include <vector>
#include <stack>
using namespace std;

/// Metoda Kosaraju
const int NMAX = 100000 + 2;
int n, m;
vector<int> ad[NMAX];
vector<int> antid[NMAX];

bool viz[NMAX];
void reset_viz(){memset(viz, 0, sizeof viz);}

stack<int> s;

vector<vector<int>> comp;

void dfs_makestack(const int x) {
    viz[x] = 1;
    for(auto v : ad[x]) {
        if(!viz[v]) {
            dfs_makestack(v);
        }
    }
    s.push(x);
}

void dfs_unwindstack(const int x) {
    viz[x] = 1;
    comp.back().push_back(x);
    for(auto v : antid[x]) {
        if(!viz[v]) {
            dfs_unwindstack(v);
        }
    }
}

int main() {
    ifstream in("ctc.in");
    ofstream out("ctc.out");
    in >> n >> m;
    for(int i = 0; i < m; i++) {
        int from, to;
        in >> from >> to;
        ad[from].push_back(to);
        antid[to].push_back(from);
    }

    /// Step 1: Build Stack
    for(int i = 1; i <= n; i++) {
        if(!viz[i]) {
            dfs_makestack(i);
        }
    }

    reset_viz();
    /// Step 2: Unwind Stack
    while(!s.empty()) {
        const int x = s.top();
        s.pop();
        if(viz[x])
            continue;
        comp.push_back({});
        dfs_unwindstack(x);
    }

    out << comp.size() << '\n';

    for(auto v : comp) {
        for(auto i : v) {
            out << i << ' ';
        }
        out << '\n';
    }
}