Cod sursa(job #3287054)

Utilizator average_disappointmentManolache Sebastian average_disappointment Data 15 martie 2025 01:00:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
//kosaraju:
//sortezi topologic
//iei de la coada sortarea si vezi daca ai muchie spre tine din alt nod
//daca ai ai gasit un ciclu => componenta conexa
//tarjan:
//la fel doar ca diferit

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 1e5;

vector<int> graph[NMAX + 1];

stack<int> s;   //asta e cu nodurile care sunt mai sus ca mine, in ordine de la cel mai apropiat
                //dar si cu alea de mai jos daca au muchie mai sus sau la mine 
                //i.e. toate care ma pot accesa

bool onstack[NMAX + 1];
int curr_idx = 1;
int idx[NMAX + 1], lowlink[NMAX + 1];
int no_components;
vector<int> components[NMAX + 1];

void dfs(int curr_node) {

    idx[curr_node] = curr_idx;
    lowlink[curr_node] = curr_idx;
    curr_idx++;

    s.push(curr_node);
    onstack[curr_node] = true;

    for (auto nxt : graph[curr_node]) {
        if (!idx[nxt]) {
            dfs(nxt);
            lowlink[curr_node] = min(lowlink[curr_node], lowlink[nxt]);
        }
        else if (onstack[nxt])  {
            lowlink[curr_node] = min(lowlink[curr_node], lowlink[nxt]);
        }
    }

    if (lowlink[curr_node] == idx[curr_node]) { //aici mi se rupe componenta
        no_components++;
        int w;
        do {
            w = s.top();
            s.pop();
            onstack[w] = false;
            components[no_components].push_back(w);
        } while (w != curr_node);
    }
}

int main() {

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

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

    cout << no_components << '\n';

    for (int i = 1; i <= no_components; i++, cout << '\n')
        for (auto node : components[i])
            cout << node << ' ';
}