Cod sursa(job #239747)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 5 ianuarie 2009 18:35:11
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>

struct nod
{
int x;
nod *urm;
};
nod *A[100001],*At[100001];
bool ok[100001];
int nr,term[100001],no[100001];

int pivot(int st,int dr)
{
int x=term[st],x1=no[st],aux;
while (st<dr)
{
while (st<dr && term[dr]<=x) dr--;
term[st] = term[dr];
no[st] = no[dr];
while (st<dr && term[st]>=x) st++;
term[dr] = term[st];
no[dr] = no[st];
}
term[st] = x;
no[st] = x1;
return st;
}


void sort(int st,int dr)
{
if (st<dr)
{
int m = pivot(st,dr);
sort(st,m-1);
sort(m+1,dr);
}
}

void DFS1(int p)
{
ok[p] = true;
while (A[p]!=NULL)
{
if (!ok[A[p]->x]) DFS1(A[p]->x);
A[p] = A[p]->urm;
}
term[p] = ++nr;
no[p] = p;
}

void DFS2(int p)
{
ok[p] = false;
while (At[p]!=NULL)
{
if (ok[At[p]->x]) DFS2(At[p]->x);
At[p] = At[p]->urm;
}
nod *urm = new nod;
urm-> x = p;
urm-> urm = A[nr];
A[nr] = urm;
}

int main()
{
FILE *in = fopen("ctc.in","r");
FILE *out = fopen("ctc.out","w");

int i,n,m,x,y;
nod *urm;
fscanf(in,"%d%d",&n,&m);
while (m)
{
m--;
fscanf(in,"%d%d",&x,&y);
urm = new nod;
urm->x = y;
urm->urm = A[x];
A[x] = urm;
urm = new nod;
urm->x = x;
urm->urm = At[y];
At[y] = urm;
}
for (i=1;i<=n;i++)
if (!ok[i]) DFS1(i);
sort(1,n);

//for (i=1;i<=n;i++) fprintf(out,"%d ",no[i]);
nr = 0;
for (i=1;i<=n;i++)
if (ok[i])
        {
         nr++;
         A[nr]=NULL;
         DFS2(i);
        }
fprintf(out,"%d\n",nr);
while (nr)
{
while (A[nr]!=NULL)
{
fprintf(out,"%d ",A[nr]->x);
A[nr]=A[nr]->urm;
}
nr--;
fprintf(out,"\n");
}
}