Pagini recente » Cod sursa (job #865639) | Cod sursa (job #2899229) | Cod sursa (job #2257556) | Cod sursa (job #1438372) | Cod sursa (job #463480)
Cod sursa(job #463480)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define dim 100000
int n,nr,nrc;
int *A[dim], *AT[dim];
int postordine[dim],viz[dim],m[dim][dim];
void citire()
{//construim graful si graful transpus
FILE *f=fopen("ctc.in","r");
int x,y,m,i;
fscanf(f,"%d%d",&n,&m);
//aloc memorie pentru gradul fiecarui varf
for(i=1;i<=n;i++)
{
A[i]=(int *) realloc(A[i],sizeof(int));
A[i][0]=0;
AT[i]=(int *) realloc(AT[i],sizeof(int));
AT[i][0]=0;
}
for(i=0;i<m;i++)
{
fscanf(f,"%d %d",&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)
{
int i;
viz[x]=1;
for(i=1;i<=A[x][0];i++)
if(!viz[A[x][i]])
DFS(A[x][i]);
postordine[++nr]=x;
}
void DEST(int x)
{
int i;
viz[x]=0; m[nrc][0]++; m[nrc][ m[nrc][0] ]=x; //printf(" %d",x);
for(i=1;i<=AT[x][0];i++)
if(viz[AT[x][i]])
DEST(AT[x][i]);
}
int main()
{
int i;
citire();
FILE *g=fopen("ctc.out","w");
//parcurgem graful DFS, determinand ordinea varfurilor
for(i=1;i<=n;i++)
if(!viz[i]) DFS(i);
//parcurgem DFS graful transpus,prelucrand varfurile in postordine
for(i=n;i>0;i--)
if(viz[postordine[i]])
//componenta tare conexa din care face parte varful curent nu a fost determinata
{
//printf("componenta tare conexa %d ",++nrc );
nrc++;
DEST(postordine[i]);
//printf("\n");
}
int j;
fprintf(g,"%d \n",nrc);
for(i=1;i<=nrc;i++)
{for(j=1;j<=m[i][0];j++)
fprintf(g,"%d ",m[i][j]);
fprintf(g,"\n");
}
return 0;
}