Cod sursa(job #752576)

Utilizator Theorytheo .c Theory Data 28 mai 2012 22:19:02
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 6.9 kb
#include<fstream>

#include<stdlib.h>

#define nmax 100010

using namespace std;

ifstream fin("ctc.in");

ofstream fout("ctc.out");

int i, j, n , m, *A[nmax], *B[nmax], *C[33333];

int  ord[nmax], nr , gr;

bool viz[nmax];

int x, y, k;



void DFS(int x)

{

    int i ;

    viz[x] = 1;



    for(i = 1 ; i <= A[x][0] ; i++)

        if(viz[A[x][i]]==0)

            DFS(A[x][i]);

    ord[++nr] = x;

}

void DFST(int x)

{

    int i;

    viz[x] = 0;

    C[gr][0]++;

    C[gr][C[gr][0]] = x;

    for(i = 1; i <= B[x][0] ;i++)

        if(viz[B[x][i]]==1)

            DFST(B[x][i]);



}

void read()

{

    int i, k ;

    fin >> n >>m ;

    for(i = 1; i <= n;i++)

    {

        A[i] = (int *) realloc(A[i], sizeof(int));

        A[i][0] = 0 ;

        B[i] = (int *) realloc(B[i], sizeof(int));

        B[i][0] = 0;



    }

    for(k = 1 ; k <= m ;k++)

    {

        fin >>i >>j ;

        A[i][0] ++;

        A[i] = (int *) realloc(A[i], (A[i][0] + 1)* sizeof(int));

        A[i][A[i][0]] = j;

        B[j][0]++;

        B[j] = (int *) realloc(B[j], (B[j][0] + 1 )* sizeof(int));

        B[j][B[j][0]] = i;

    }

    for(i = 1; i <= n;i++)

        if(viz[i] ==0 )

            DFS(i);

    for(i = n; i ; i--)

        if(viz[ord[i]])

        {

            gr++;

           // C[gr][0] = 0 ;

            C[gr] = (int *) realloc(C[gr], sizeof(int));

            C[gr][0]= 0;



             DFST(ord[i]);

        }



}

void display()

{

    int i, j ;

    fout << gr <<'\n';

    for(i = 1; i <= gr; i++)

    {

         for(j = 1; j <= C[i][0]; j++)

            fout<< C[i][j] <<" ";

        fout <<'\n' ;

    }





}

int main()

{

    read();

    display();

    fin.close();

    fout.close();

    return 0;

}