Pagini recente » Cod sursa (job #2550021) | Cod sursa (job #1609440) | Cod sursa (job #1195211) | Cod sursa (job #175473) | Cod sursa (job #7135)
Cod sursa(job #7135)
#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);
}