Cod sursa(job #2925519)

Utilizator RobertuRobert Udrea Robertu Data 15 octombrie 2022 15:41:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.56 kb
/*
    Link: https://www.infoarena.ro/problema/ctc
    Idee: Am aplicat algoritmul lui Tarjan
    Complexitate: O(n + m)
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define dim 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, a, b, cnt = 0, id = 0;
vector< vector<int> > lists(dim);
vector<bool> onStack(dim);             //verificam mai usor existenta pe stiva
vector<int> low(dim), disc(dim);       //vectorii de low-key si dicover
stack<int> stk;                        //stiva necesara obtinerii corecte a componentelor
vector< vector<int> > sol(dim); 


/*
    Fiecare nod parcurs e pus pe stiva si initiala lui valoare low-key este cea de discover.
    Aplicam acelasi lucru si pt vecini, pana ajungem la smecheria algoritmului:
        -cand suntem pe o muchie de intoarcere, actualizam low-key ul nodului curent
        dupa formula 'low[nod] = min(low[nod], low[vecin])', DOAR DACA vecinul se afla pe stiva,
        adica este valid pt componenta actuala ( din el se poate ajunge la nodul curent )

        -cand epuizam vecinii unui nod, verificam daca am inchis o componenta, conditia de inchidere
        fiind 'disc[nod] == low[nod]'. Daca da, scoatem de pe stiva toate nodurile pana ajungem la cel 
        curent (noduri care alcatuiesc componenta tare conexa), si le actualizam low-key ul, ca se le
        grupam la final
*/
void tarjan(int nod) {
    stk.push(nod);
    onStack[nod] = true;
    disc[nod] = low[nod] = ++id;

    for (int i = 0; i < lists[nod].size(); i++) {
        int vecin = lists[nod][i];

        if (disc[vecin] == 0) {
            tarjan(vecin);
        }

        if( onStack[vecin] ) {
            low[nod] = min(low[nod], low[vecin]);
        }
    }

    if (disc[nod] == low[nod]) {
        while (stk.top() != nod) {
            onStack[stk.top()] = false;
            low[stk.top()] = disc[nod];
            stk.pop();
        }

        onStack[stk.top()] = false;
        low[stk.top()] = disc[nod];
        stk.pop();

        cnt++;
    }
}

int main() {
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        fin >> a >> b;
        lists[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {
        if (disc[i] == 0) {
            tarjan(i);
        }
    }

    for(int i = 1; i <= n; i++)
        sol[ low[i] ].push_back(i);

    fout << cnt << '\n';

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

    return 0;
}