Cod sursa(job #1662340)

Utilizator cristina_borzaCristina Borza cristina_borza Data 24 martie 2016 18:02:03
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <cstring>
#include <vector>

#define NMAX 200005

using namespace std;

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

int lst[NMAX] , urm[NMAX] , vf[NMAX] , lstt[NMAX] , vft[NMAX] , urmt[NMAX] , viz[NMAX] , ctc[NMAX];
int n , m , nr , nrc , x , y , nrt;

vector <vector <int> > c;

void dfs(int x);
void dfst(int x);
void adauga(int pos , int x);

int main() {
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++i) {
        f >> x >> y;

        ++nr;
        vf[nr] = y;
        urm[nr] = lst[x];
        lst[x] = nr;


        ++nrt;
        vft[nrt] = y;
        urmt[nrt] = lstt[x];
        lstt[x] = nrt;
    }

    for(int i = 1 ; i <= n ; ++i) {
        if(viz[i] == 0) {
            dfs(i);
        }
    }
    memset(viz , 0 , sizeof(viz));

    c.resize(nrc + 5);
    nr = 0;
    for(int i = 1 ; i <= n ; ++i) {
        if(viz[ctc[i]] == 0) {
            ++nr;
            dfst(ctc[i]);
        }
    }

    g << nr << '\n';
    for(int i = 1 ; i <= nr ; ++i) {
        //g << c[i].size() << " ";
        for(vector <int> :: iterator  it = c[i].begin() ; it != c[i].end() ; ++it) {
            g << *it << " ";
        }
        g << '\n';
    }

    return 0;
}

void dfs(int x) {
    viz[x] = 1;
    int p , y;
    p = lst[x];
    while(p != 0) {
        y = vf[p];
        if(!viz[y]) {
            dfs(y);
        }
        p = urm[p];
    }

    ctc[++nrc] = x;
}

void dfst(int x) {
    viz[x] = 1;
    int p , y;
    p = lstt[x];
    adauga(nr , x);
    while(p != 0) {
        y = vft[p];
        if(!viz[y]) {
            dfst(y);
        }
        p = urmt[p];
    }
}

void adauga(int pos , int x) {
    c[pos].push_back(x);
}