Cod sursa(job #2925516)

Utilizator RobertuRobert Udrea Robertu Data 15 octombrie 2022 15:32:03
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 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


/*
    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);
        }
    }

    fout << cnt << "\n" << 1;

    for(int i = 2; i <= n; i++) {
        if( low[i] == low[i - 1] )
            fout << " " << i;
        else fout << '\n' << i;
    }

    // fout << '\n';

    return 0;
}