Cod sursa(job #694298)

Utilizator bogdanbearBOGDAN bogdanbear Data 27 februarie 2012 19:44:10
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
using namespace std;
FILE *in=fopen("ctc.in","r");
FILE *out=fopen("ctc.out","w");
struct nod {int dest;nod *leg;};
nod *a[10000],*t[10000],*p;
int n,m,i,j,x,y,stack[10000],top,end,ord,mark[10000],sign[10000];
void adees(int k)
{mark[k]=i;
nod *point; 
point=a[k];
 while (point!=NULL)
	 {if (mark[point->dest]==0)
		 adees(point->dest);
		point=point->leg;
	 }
stack[++top]=k;
}

void tdfs(int k)
{sign[k]=ord;
 
nod *point; 
point=t[k];
 while (point!=NULL)
	 {if (sign[point->dest]==0)
		 tdfs(point->dest);
		point=point->leg;
	 }

}




int main()
{fscanf(in,"%d %d",&n,&m);

for (i=1;i<=n;i++){a[i]=NULL;t[i]=NULL;}

for (i=1;i<=m;i++)
{fscanf(in,"%d %d",&x,&y);
p=new(nod);
p->dest=y;
p->leg=a[x];

a[x]=p;
p=new(nod);
p->dest=x;
p->leg=t[y];

t[y]=p;
}
//end reading



top=0;i=1;
while(top<n)
{
	if (mark[i]==0)
adees(i);
i++;
}

ord=0;
for (i=top;i>=1;i--)
if (sign[stack[i]]==0){ord++;
							tdfs(stack[i]);}

for (i=1;i<=n;i++)
	{fprintf(out,"%d ",i);
	if ((mark[i]!=mark[i+1])or(sign[i]!=sign[i+1])) fprintf(out,"%c",'\n');
	}


fclose(in);fclose(out);
return 0;
}