Cod sursa(job #739439)

Utilizator Theorytheo .c Theory Data 23 aprilie 2012 01:28:01
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<fstream>
#include<stdlib.h>
#define nmax 50010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int i, j, n , m, *A[nmax], *B[nmax], *C[nmax];
int viz[nmax], ord[nmax], nr , gr;
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;
        C[i] = (int *) realloc(C[i], sizeof(int));
        C[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++;
             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;
}