Cod sursa(job #2929716)

Utilizator mihai03Mihai Grigore mihai03 Data 26 octombrie 2022 17:46:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
// 242 - Grigore Mihai-Catalin
// componente tare conexe
// algoritmul lui kosaraju
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int maxx = 100005;

vector < vector < int > > graf, grafTranspus;
int nodVizitat[maxx];
int timpiFinalizare[maxx], cntTimpi;

vector < vector < int > > componenteTareConexe;
int nrComponenteTareConexe;

void setareVizitati(int n) {
    // setez toate nodurile ca fiind nevizitate
    for (int i = 1; i <= n; ++i) {
        nodVizitat[i] = 0;
    }
}

void parcurgereDFS(int k) {
    nodVizitat[k] = 1;
    for (int i = 0; i < graf[k].size(); ++i) {
        if (nodVizitat[graf[k][i]] == 0) {
            parcurgereDFS(graf[k][i]);
        }
    }
    timpiFinalizare[cntTimpi++] = k;
}

void parcurgereGrafTranspus(int k) {
    nodVizitat[k] = 1;
    componenteTareConexe[nrComponenteTareConexe].push_back(k);
    for (int i = 0; i < grafTranspus[k].size(); ++i) {
        if (!nodVizitat[grafTranspus[k][i]]) {
            parcurgereGrafTranspus(grafTranspus[k][i]);
        }
    }
}

int main() {
    ifstream f("ctc.in");
    ofstream g("ctc.out");

    int n, m;
    f >> n >> m;
    graf = vector < vector < int > > (n + 1);
    grafTranspus = vector < vector < int > > (n + 1);
    componenteTareConexe = vector < vector < int > > (n + 1);
//  cout << n << " " << m << "\n";

    int x, y;
    for (int i = 0; i < m; ++i) {
        f >> x >> y;
//      cout << x << " " << y << "\n";
        graf[x].push_back(y);
        grafTranspus[y].push_back(x);
    }

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

    setareVizitati(n);

    int nrComponenteConexe = 0;
//    cout << cntTimpi << "\n";
//    for (int i = cntTimpi - 1; i >= 0; --i) {
//        cout << timpiFinalizare[i] << " ";
//    }

    for (int i = cntTimpi - 1; i >= 0; --i) {
        if (nodVizitat[timpiFinalizare[i]] == 0) {
            parcurgereGrafTranspus(timpiFinalizare[i]);
            ++nrComponenteTareConexe;
        }
    }

    g << nrComponenteTareConexe << "\n";

    for (int i = 0; i < nrComponenteTareConexe; ++i) {
        for (int j = 0; j < componenteTareConexe[i].size(); ++j) {
            g << componenteTareConexe[i][j] << " ";
        }
        g << "\n";
    }

    return 0;
}