Cod sursa(job #2909322)

Utilizator ctrohinCristina Trohin ctrohin Data 12 iunie 2022 18:47:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;

int n, m;
vector <int> adj[NMAX];
bool viz[NMAX],inStack[NMAX];
int timestamp;
int found[NMAX], low_link[NMAX];
stack <int> nodes_stack;
vector <vector <int> > all_scc;

void dfs(int x) {
    found[x] = low_link[x] = timestamp++;
    nodes_stack.push(x);
    inStack[x] = 1;
    viz[x] = 1;

    for (auto y : adj[x]) {
        if (!viz[y]) {
            dfs(y);
            low_link[x] = min(low_link[x], low_link[y]);
        } else {
            if (inStack[y]) {
                low_link[x] = min(low_link[x], low_link[y]);
            }
        }
    }

    vector <int> scc;
    int el;
    if (low_link[x] == found[x]) {
        do {
            el = nodes_stack.top();
            inStack[el] = 0;
            nodes_stack.pop();
            scc.push_back(el);
        } while (el != x);
        all_scc.push_back(scc);
    }

}

int main() {
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");

    cin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
    }

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

    cout << all_scc.size() << endl;

    for (auto scc : all_scc) {
        for (auto node : scc) {
            cout << node << " ";
        }
        cout << "\n";
    }
}