Cod sursa(job #862711)

Utilizator evodaniVasile Daniel evodani Data 22 ianuarie 2013 21:14:49
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin ("ctc.in"); ofstream fout ("ctc.out");
short int *mat[25001];
short int n, m, i, a, b, ct, cc, post[25001], j;
bool viz[25001];
short int *trans[25001];
short int *comp[25001];
void dfs (short int s) {
    short int i;
    viz[s]=1;
    for (i=1; i<=mat[s][0]; ++i) if (!viz[mat[s][i]]) dfs(mat[s][i]);
    post[++ct]=s;
}
void dfst (short int s) {
    short int i;
    comp[cc]=(short int*)realloc(comp[cc], (++comp[cc][0]+1)*sizeof(short int));
    comp[cc][comp[cc][0]]=s;
    viz[s]=0; for (i=1; i<=trans[s][0]; ++i) if (viz[trans[s][i]]) dfst(trans[s][i]);
}
int main()
{
    //algoritm folosit pentru determinarea componentelor tare-conexe
    //parcurge graful DFS si retine ordinea varfurilor parcurse in postordine

    //se parcurge apoi graful transpus dupa lista postordonata a varfurilor,
    //in ordine INVERSA, componentele identificate fiind de natura tare conexa
    fin>>n>>m;
    for (i=1; i<=n; ++i) {
        mat[i]=(short int*)realloc(mat[i], sizeof(short int)); mat[i][0]=0;
        trans[i]=(short int*)realloc(trans[i], sizeof(short int)); trans[i][0]=0;
        comp[i]=(short int*)realloc(comp[i], sizeof(short int)); comp[i][0]=0;
    }
    for (i=1; i<=m; ++i) {
        fin>>a>>b;
        mat[a]=(short int*)realloc(mat[a], (++mat[a][0]+1)*sizeof(short int)); mat[a][mat[a][0]]=b;
        trans[b]=(short int*)realloc(trans[b], (++trans[b][0]+1)*sizeof(short int)); trans[b][trans[b][0]]=a;
    }
    for (i=1; i<=n; ++i) if (!viz[i]) dfs(i);
    for (i=n; i>=1; --i) if (viz[post[i]]) {
        ++cc;
        dfst(post[i]);
    }
    fout<<cc<<'\n'; for (i=1; i<=cc; ++i) { for (j=1; j<=comp[i][0]; ++j) fout<<comp[i][j]<<' '; fout<<'\n'; }
    fout.close();
    return 0;
}