Pagini recente » Cod sursa (job #384956) | Cod sursa (job #1185302) | Cod sursa (job #403648) | Cod sursa (job #1301920) | Cod sursa (job #295879)
Cod sursa(job #295879)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 100005
int *L[NMAX],c[NMAX],elem[NMAX],INDEX[NMAX],low[NMAX],S[NMAX];
int n,nc,ne,nrord,ns;
int inSt[NMAX];
void citire()
{
FILE *fin=fopen("ctc.in","r");
int m,i;
fscanf(fin,"%d%d",&n,&m);
for (i=1;i<=n;++i)
{ L[i]=(int*)realloc(L[i],sizeof(int)); L[i][0]=0; }
while (m--)
{ int x,y;
fscanf(fin,"%d %d",&x,&y);
L[x][0]++;
L[x]=(int*) realloc(L[x],(L[x][0]+1)*sizeof(int));
L[x][L[x][0]]=y;
}
fclose(fin);
}
void afisare()
{
FILE *fout=fopen("ctc.out","w");
fprintf(fout,"%d",nc);
c[0]=0;
int i;
for (i=1;i<=n;++i)
{
if (c[i]!=c[i-1]) fprintf(fout,"\n");
fprintf(fout,"%d ",elem[i]);
}
fclose(fout);
}
inline int min(int a, int b)
{
if (a<b) return a;
return b;
}
void tarjan(int v)
{ int i;
INDEX[v]=low[v]=++nrord;
S[++ns]=v;inSt[v]=1;
for (i=1;i<=L[v][0];++i)
{
int w=L[v][i];
if (!INDEX[w] || inSt[w])
{
if (!INDEX[w]) tarjan(w);
low[v]=min(low[v],low[w]);
}
}
int w;
if (low[v]==INDEX[v])
{ nc++;
do
{
w=S[ns--]; inSt[w]=0;
elem[++ne]=w; c[ne]=nc;
}
while (w!=v);
}
}
int main()
{
citire();
ns=0; nrord=0; ne=0;
memset(INDEX,0,sizeof(INDEX));
memset(inSt,0,sizeof(inSt));
int i;
for (i=1;i<=n;++i)
if (!INDEX[i]) tarjan(i);
afisare();
return 0;
}