Cod sursa(job #876030)

Utilizator FayedStratulat Alexandru Fayed Data 11 februarie 2013 09:17:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <stdlib.h>
using namespace std;

int n,m,k,nr;
int * V[100001];
int * Vt[100001];
int *M[100001];
int vizitat[100001],sol[100001];

void citesc(){

    freopen("ctc.in","r",stdin);
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){

        V[i] = (int*) realloc(V[i],sizeof(int));
        V[i][0] = 0;
        Vt[i]= (int*) realloc(Vt[i],sizeof(int));
        Vt[i][0] = 0;
    }

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

    scanf("%d%d",&x,&y);
    V[x][0]++;
    V[x] = (int*)realloc(V[x],(V[x][0]+1)*sizeof(int));
    V[x][V[x][0]] = y;
    Vt[y][0]++;
    Vt[y] = (int*)realloc(Vt[y],(Vt[y][0]+1)*sizeof(int));
    Vt[y][Vt[y][0]] = x;
    }

}

void DFS(int nod){

    vizitat[nod] = 1;
    for(int i=1;i<=V[nod][0];i++)
        if(!vizitat[V[nod][i]])
            DFS(V[nod][i]);
sol[++k] = nod;
}

void DFST(int nod){

    vizitat[nod] = 0;
    M[nr][0]++;
    M[nr] = (int*)realloc(M[nr],(M[nr][0]+1)*sizeof(int));
    M[nr][M[nr][0]] = nod;

    for(int i=1;i<=Vt[nod][0];i++)
        if(vizitat[Vt[nod][i]])
            DFST(Vt[nod][i]);
}

int main(){

    citesc();
    freopen("ctc.out","w",stdout);

        for(int i=1;i<=n;i++)
            if(!vizitat[i])
                DFS(i);

        for(int i=n;i>0;i--)
            if(vizitat[sol[i]]){
                ++nr;
                M[nr] = (int*)realloc(M[nr],sizeof(int));
                M[nr][0] = 0;
                    DFST(sol[i]);
        }
printf("%d\n",nr);
    for(int i =1;i<=nr;i++){
        for(int j=1;j<=M[i][0];j++)
            printf("%d ", M[i][j]);
          printf("\n");
    }
 return 0;

}