Cod sursa(job #1726380)

Utilizator preda.andreiPreda Andrei preda.andrei Data 7 iulie 2016 21:23:37
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define NMAX 100000

struct Nod
{
    int index;
    int lowerBound;
    bool vizitat;
    vector<int> vecini;
};

Nod noduri[NMAX + 1];
vector<int> stiva;
vector< vector<int> > componente;
int timp = 0;

void tarjan(int nod);

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int n, m;
    fin >> n >> m;

    while (m--) {
        int x, y;
        fin >> x >> y;
        noduri[x].vecini.push_back(y);
    }

    for (int i = 1; i <= n; ++i) {
        if (!noduri[i].vizitat) {
            tarjan(i);
        }
    }

    fout << componente.size() << "\n";
    for (auto componenta : componente) {
        for (int nod : componenta)
            fout << nod << " ";
        fout << "\n";
    }

    return 0;
}

void tarjan(int nod)
{
    stiva.push_back(nod);
    noduri[nod].index = noduri[nod].lowerBound = ++timp;
    noduri[nod].vizitat = true;

    for (int vecin : noduri[nod].vecini) {
        if (!noduri[vecin].vizitat)
            tarjan(vecin);
        noduri[nod].lowerBound = min(noduri[nod].lowerBound, noduri[vecin].lowerBound);
    }

    if (noduri[nod].lowerBound == noduri[nod].index) {
        vector<int> componentaNoua;

        do {
            componentaNoua.push_back(stiva.back());
            stiva.pop_back();
        } while (componentaNoua.back() != nod);

        componente.push_back(componentaNoua);
    }
}