Cod sursa(job #619969)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 16 octombrie 2011 11:04:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<vector>
#include<fstream>
#define N 100010
using namespace std;

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

int n,m,final[N],ordine[N],nr;
vector<int> g[N],gt[N],tc[N];
bool vizitat[N];

void df_final(int nod,int &timp) {
    vector<int>::iterator i;

    for(i=g[nod].begin();i!=g[nod].end();++i) if(!vizitat[*i]) {

        vizitat[*i]=true;
        df_final(*i,timp);

        ++timp;
    }

    final[nod]=timp;
}

void df(int nod) {
    vector<int>::iterator i;

    for(i=gt[nod].begin();i!=gt[nod].end();++i) if(!vizitat[*i]) {
        vizitat[*i]=true;

        tc[nr].push_back(*i);

        df(*i);
    }
}

int main() {
    int i,a,b,timp=1;

    in >> n >> m;

    for(i=1;i<=m;++i) {

        in >> a >> b;

        g[a].push_back(b);
        gt[b].push_back(a);

    }

    for(i=1;i<=n;++i) if(!vizitat[i]) {
        vizitat[i]=true;
        df_final(i,timp);
    }

    for(i=1;i<=n;++i) {
        ordine[n-final[i]+1]=i;

        vizitat[i]=false;
    }

    for(i=1;i<=n;++i) if(!vizitat[ordine[i]]) {
        vizitat[i]=true;
        ++nr;
        tc[nr].push_back(i);
        df(i);
    }

    out << nr << "\n";
    vector<int>::iterator it;

    for(i=1;i<=nr;++i) {
        for(it=tc[i].begin();it!=tc[i].end();++it)
            out << *it << " ";

        out << "\n";
    }

    return 0;
}