Cod sursa(job #2428947)

Utilizator florinel2102florin pricopie florinel2102 Data 6 iunie 2019 22:46:35
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
#define infile "ctc.in"
#define outfile "ctc.out"
int n , nr ,nrc;
int *D[NMAX];
int *A[NMAX];
int *AT[NMAX];
int postordine[NMAX];
bool viz[NMAX];

void citire();
void DFS(int);
void DFST(int);

int main()
{
    citire();
    ofstream fout(outfile);
    for(int i=1;i<=n;++i)
    {
        if(!viz[i])
            DFS(i);
    }
    for(int i=nr;i>0;--i)
    {
        if(viz[postordine[i]])
        {
            ++nrc;
            D[nrc] = (int *) malloc(sizeof(int));
            D[nrc][0]=0;
            DFST(postordine[i]);
        }
    }
    fout<<nrc<<endl;
    for(int i=1;i<=nrc;++i)
    {
        for(int j=1;j<=D[i][0];++j)
            fout<<D[i][j]<<' ';
        fout<<endl;
    }
}

void citire()
{
    ifstream fin(infile);
    int m , x , y;
    fin>>n>>m;
  //  postordine = (int *)malloc((n+1)*sizeof(int));
  //  viz = (bool *)malloc((n+1)*sizeof(bool));
    for(int i=1;i<=n;++i)
    {
        A[i] = (int *) malloc(sizeof(int));
        A[i][0]= 0;
        AT[i] =(int *) malloc(sizeof(int));
        AT[i][0]= 0;
    }
    for(int i=0;i<m;++i)
    {
        fin>>x>>y;
        A[x][0]++;
        A[x] = (int *) realloc(A[x],(A[x][0]+1)*sizeof(int));
        A[x][A[x][0]] = y;
        AT[y][0]++;
        AT[y] = (int *) realloc(AT[y],(AT[y][0]+1)*sizeof(int));
        AT[y][AT[y][0]] = x;
    }
}

void DFS(int x)
{
    viz[x]=1;
    for(int i=1;i<=A[x][0] ; ++i)
    {
        if(!viz[A[x][i]])
            DFS(A[x][i]);
    }
    postordine[++nr]=x;
}

void DFST(int x)
{
    viz[x]=0;

    D[nrc][0]++;
    D[nrc] =(int *) realloc(D[nrc],(D[nrc][0]+1)*sizeof(int));
    D[nrc][D[nrc][0]] = x;

    for(int i=1;i<=AT[x][0];++i)
    {
        if(viz[AT[x][i]])
            DFST(AT[x][i]);
    }
}