Cod sursa(job #1267783)

Utilizator diana97Diana Ghinea diana97 Data 20 noiembrie 2014 12:05:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100000 + 1;

int n, m, index_crt, comp;
vector <int> graf[NMAX];
stack <int> stiva;
int eticheta[NMAX], intoarcere[NMAX];
bool in_stiva[NMAX];
vector < vector <int> > componente;

void citeste() {
    int a, b;
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> a >> b;
        graf[a].push_back(b);
    }
}

void tarjan(int nod) {
    eticheta[nod] = intoarcere[nod] = ++index_crt;
    int fiu, l = graf[nod].size();
    stiva.push(nod); in_stiva[nod] = true;

    for (int i = 0; i < l; i++) {
        fiu = graf[nod][i];
        if (eticheta[fiu] == 0) tarjan(fiu);
        if (in_stiva[fiu]) intoarcere[nod] = min(intoarcere[nod], intoarcere[fiu]);
    }
    if (intoarcere[nod] >= eticheta[nod]) {
        comp++;
        int top;
        vector <int> componenta_curenta;
        do {
            top = stiva.top();
            stiva.pop(); in_stiva[top] = false;
            componenta_curenta.push_back(top);
        } while (top != nod);
        componente.push_back(componenta_curenta);
    }
}


void scrie() {
    int a, b;
    a = componente.size(); g << a << '\n';
    for (int i = 0; i < a; i++) {
        b = componente[i].size();
        for (int j = 0; j < b; j++) g << componente[i][j] << ' ';
        g << '\n';
    }
}

int main() {
    citeste();
    for (int i = 1; i <= n; i++)
        if (!eticheta[i]) tarjan(i);
    scrie();
    return 0;
}