Cod sursa(job #7135)

Utilizator rusRus Sergiu rus Data 21 ianuarie 2007 12:45:43
Problema Triplete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.56 kb
#include<stdio.h>
#include<stdlib.h>
#define max 16001

int n,nr,nrc;

int *a[max],*at[max];
int postordine[max],viz[max];

void citire();
void dfs(int );
void dfst(int );
void afisare();
int main()
{
    freopen("triplete.in","r",stdin);
    freopen("triplete.out","w",stdout);
    int i;
    citire();
    
    for(i=1;i<=n;i++)
    if(!viz[i]) dfs(i);
    for(i=n;i>0;i--)
    if(viz[postordine[i]])
    {
                          ++nrc;
                          dfst(postordine[i]);
    }
    afisare();
    return 0;
}
void citire()
{
     int x,y,m,i;
     scanf("%d %d",&n,&m);
     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++)
     {
                     scanf("%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 dfst(int x)
{
     int i;
     viz[x]=0;
     //printf("%d ",x);
     for(i=1;i<=at[x][0];i++)
     if(viz[at[x][i]])
       dfst(at[x][i]);
}
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 afisare()
{
     printf("%d",nrc);
}