Cod sursa(job #1377094)

Utilizator diana97Diana Ghinea diana97 Data 5 martie 2015 20:04:49
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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, nrcomp;
int lowlink[NMAX], index[NMAX];
bool in_stack[NMAX];
int comp[NMAX];
stack <int> st;
vector <int> graf[NMAX];

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) {
    int l = graf[nod].size(), fiu, top;

    index[nod] = lowlink[nod] = ++index_crt;
    st.push(nod); in_stack[nod] = true;

    for (int i = 0; i < l; i++) {
        fiu = graf[nod][i];
        if (!index[fiu]) tarjan(fiu);
        if (in_stack[fiu]) lowlink[nod] = min(lowlink[nod], lowlink[fiu]);
    }

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

void scrie() {
    g << nrcomp << '\n';
    for (int i = 1; i <= nrcomp; i++, g << '\n')
        for (int j = 1; j <= n; j++)
            if (i == comp[j]) g << j << ' ';
}


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