Cod sursa(job #1662365)

Utilizator andrei_bB. Andrei andrei_b Data 24 martie 2016 18:33:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax=100005;
const int Mmax=200005;

vector <int> v[100005];

int n,m,a,b,nr,nc,nrc;
int vf[Mmax],urm[Mmax],lst[Nmax],vft[Mmax],urmt[Mmax],lstt[Nmax],c[Nmax];
bool viz[Nmax];

void adauga ( int x , int y ){

    nr++;

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

    vft[nr]=x;
    urmt[nr]=lstt[y];
    lstt[y]=nr;

}

void dfs ( int x ){

    viz[x]=true;
    int p,y;
    p=lst[x];

    while ( p != 0 ){
        y=vf[p];
        if ( !viz[y] )
            dfs(y);
        p=urm[p];
    }
    c[++nc]=x;
}

void dfst ( int x ){

    viz[x]=true;
    int p,y;

    p=lstt[x];
    v[nrc].push_back(x);

    while ( p != 0 ){
        y=vft[p];
        if ( !viz[y] )
            dfst(y);
        p=urmt[p];
    }
}

int main()
{
    fin>>n>>m;
    for ( int i=1 ; i<=m ; i++ ){
        fin>>a>>b;
        adauga(a,b);
    }

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

    for ( int i=1 ; i<=n ; i++ ){
        viz[i]=false;

    }

    for ( int i=n ; i>=1 ; i-- ){
        if ( !viz[c[i]] ){
            ++nrc;
            dfst(c[i]);
        }
    }

    fout<<nrc<<'\n';
    for ( int i=1 ; i<=nrc ; i++ ){
       for ( int j=0 ; j<v[i].size() ; j++ ){
            fout<<v[i][j]<<' ';
        }
        fout<<'\n';
    }
}