Cod sursa(job #1831955)

Utilizator NinjaCubeMihai Radovici NinjaCube Data 19 decembrie 2016 10:13:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

#define DIM 100005

vector <vector <int> > G, Rez;
int tmp = 1, N, M, x, y;
int Timp[DIM], Best[DIM], viz[DIM], St[DIM], eSt[DIM];

void DF(int nod);

int main() {
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    scanf("%d %d\n", &N, &M);

    G.resize(N + 2);

    for(int i = 1; i <= M; ++i) {
        scanf("%d %d\n", &x, &y);

        G[x].push_back(y);
    }

    for(int i = 1; i <= N; ++i) {
        if(!viz[i]) {
            DF(i);
        }
    }

    cout << Rez.size() << '\n';

    for(unsigned int c = 0; c < Rez.size(); ++c) {
        for(unsigned int z = 0; z < Rez[c].size(); ++z) {
            cout << Rez[c][z] << ' ';
        }

        cout << '\n';
    }

    return 0;
}

void DF(int nod) {
    viz[nod] = 1;
    St[++St[0]] = nod;
    eSt[nod] = 1;

    Timp[nod] = tmp;
    Best[nod] = tmp++;

    for(unsigned int z = 0; z < G[nod].size(); ++z) {
        if(!viz[G[nod][z]]) {
            DF(G[nod][z]);
            Best[nod] = min(Best[nod], Best[G[nod][z]]);
        }
        else {
            if(eSt[G[nod][z]] == 1) {
                Best[nod] = min(Best[nod], Best[G[nod][z]]);
            }
        }
    }

    if(Best[nod] == Timp[nod]) {
        vector <int> x;

        while(St[St[0]] != nod) {
            x.push_back(St[St[0]]);
            eSt[St[St[0]]] = 0;
            --St[0];
        }

        x.push_back(nod);

        Rez.push_back(x);

        eSt[nod] = 0;
        --St[0];
    }
}