Cod sursa(job #1241001)

Utilizator diana97Diana Ghinea diana97 Data 12 octombrie 2014 14:26:11
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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, indexCrt, nrcomp;
int index[NMAX], lowlink[NMAX];
bool instack[NMAX];
vector <int> v[NMAX];
vector <int> comp[NMAX];
stack <int> st;

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

void tarjan(int nod) {
    index[nod] = lowlink[nod] = ++indexCrt;
    st.push(nod);
    instack[nod] = 1;
    int nod2, l = v[nod].size();
    for (int i = 0; i < l; i++) {
        nod2 = v[nod][i];
        if (index[nod2] == 0) tarjan(nod2);
        if (index[nod2] > 0) lowlink[nod] = min(lowlink[nod], lowlink[nod2]);
    }

    if (lowlink[nod] >= index[nod]) {
        nrcomp++;
        //comp[nrcomp].push_back(nod);
        do{
            nod2 = st.top(); st.pop();
            comp[nrcomp].push_back(nod2);
        } while (nod2 != nod);
    }
}

void scrie() {
    int l;
    g << nrcomp << '\n';
    for (int i = 1; i <= nrcomp; i++) {
        l = comp[i].size();
        for (int j = 0; j < l; j++) g << comp[i][j] << ' ';
        g << '\n';
    }
}

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