Cod sursa(job #638890)

Utilizator vendettaSalajan Razvan vendetta Data 21 noiembrie 2011 20:29:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#define nmax 100011
#include <deque>
#include <vector>
#include <bitset>

using namespace std;

vector<int> gf[nmax];
deque<int> Dq;
vector<int> sol[nmax];
int nr_ctc;
int n,m;
int index= 0;
int id[nmax], low_link[nmax];
bitset<nmax> viz;

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

void citeste(){

    f>>n>>m;
    for(int i=1; i<=m; ++i){
        int x,y;
        f>>x>>y;
        gf[x].push_back(y);
    }

}

int minim(int a, int b){

    if (a > b) return b;
    return a;

}

void tarjan(int nod){

    ++index;
    id[nod] = index;
    low_link[nod] = index;
    Dq.push_back(nod);
    viz[nod] = 1;

    for(unsigned i=0; i < gf[nod].size(); ++i){
        int vecin = gf[nod][i];
        if (id[vecin] == -1){
            tarjan( vecin );
            low_link[nod] = minim(low_link[nod], low_link[vecin]);
        }else if (viz[vecin] == 1){
            low_link[nod] = minim(low_link[nod], id[vecin]);
        }
    }

    if (low_link[nod] == id[nod]){
        int w = Dq.back();
        Dq.pop_back();
        viz[w] = 0;
        ++nr_ctc;
        sol[nr_ctc].push_back(w);
        while (w != nod){
            w = Dq.back();
            Dq.pop_back();
            viz[w] = 0;
            sol[nr_ctc].push_back(w);
        }
    }

}

void rezolva(){

    for(int i=0; i<=n; ++i) id[i] = -1;


    for(int i=1; i<=n; ++i){
        if (id[i] == -1)
            tarjan(i);
    }

}

void scrie(){

    g<<nr_ctc<<"\n";

    for(int i=1; i<=nr_ctc; ++i){
        for(unsigned j=0; j < sol[i].size(); ++j)
            g<<sol[i][j]<<" ";
        g<<"\n";
    }

}


int main(){


    citeste();
    rezolva();
    scrie();

    f.close();
    g.close();


    return 0;

}