Cod sursa(job #3317594)

Utilizator pstgarain ploaie pstga Data 24 octombrie 2025 15:47:49
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

// declararea variabilelor
const int MAXN = 10000;   // adjust for your graph size

vector<int> adj[MAXN];    // lista de adiacenta
int indexVal[MAXN];       // indexul la care am descoperit nodul - ordinea in care "descopar" nodurile in parcurgere
int lowlink[MAXN];        // low
bool onStack[MAXN];       // if on stack true else false ig - daca e on stack e in componenta tare conexa
stack<int> st;            // stack
int currentIndex = 0;     // global index
vector<vector<int>> sccs; // lista de output; componentele tare conexe
int n, m;                 // nr noduri

// algoritmul lui tarjan: functia care "conecteaza propriu zis" nodurile cu aj arcelor
void strongConnect(int v) {
    indexVal[v] = lowlink[v] = currentIndex++; // index si low sunt initializate cu nivelul pe care ne aflam; low se poate actualiza
    st.push(v); // punem pe stack si confirmam in vector ca e onstack
    onStack[v] = true;

    // trecem prin vecini
    for (int w : adj[v]) {
        if (indexVal[w] == -1) {
            // ca la noduri de intersectie trecem prin el recursiv si vedem daca putem sau nu sa actualizam low ul
            strongConnect(w);
            lowlink[v] = min(lowlink[v], lowlink[w]); // minim dintre low ul sau de acum SAU cel de la copilul sau
        }
        else if (onStack[w]) {
            // daca e deja on stack inseamna ca face parte deja din aceasta compoonenta tare conexa, deci poate pot update ui minimul.
            lowlink[v] = min(lowlink[v], indexVal[w]);
        }
    }

    // daca am acelasi low cu nivel inseamna ca e root ul unei componente tare conexe ( = cu cazul in care e izolat si singur)
    if (lowlink[v] == indexVal[v]) {
        // creem o noua componenta tare conexa!
        vector<int> scc;
        int w;
        // punem de pe stack toate nodurile din componenta in "scc" care e temp ul meu pt componenta
        do {
            w = st.top();
            st.pop();
            onStack[w] = false; // scoatem si din vector
            scc.push_back(w);
        } while (w != v); // pana ajungem la v adica rootul meu
        sccs.push_back(scc); // bagam in rezultate
    }
}

// efectiv algoritmul de run prin toate nodurile
void tarjanSCC() {
    for (int v = 1; v <= n; ++v) {
        if (indexVal[v] == -1) // daca n a fost vizitat pana acum
            strongConnect(v);
    }
}

int main() {
    // initializare si citire de date
    fin >> n >> m;

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

    for (int i = 1; i <= n ; ++i) {
        indexVal[i] = -1; // initializat cu -1 pt nevizitat
        lowlink[i] = 0;
        onStack[i] = false;
    }

    tarjanSCC();

    // afisare
    fout << sccs.size() << endl;
    for (auto &scc : sccs) {
        for (int v : scc)
            fout << v << " ";
        fout << "\n";
    }

    return 0;
}