Pagini recente » Cod sursa (job #2115767) | Cod sursa (job #689783) | Cod sursa (job #2424147) | Cod sursa (job #1218673) | Cod sursa (job #369231)
Cod sursa(job #369231)
#include <stdio.h>
#define max 100005
struct lista
{
int nod;
lista *urm;
};
lista *g[max],*gt[max],*p;
int postordine[max],i,j,n,m,nr,nrcp;
char s[max];
void dfs(int nod)
{
lista *p;
s[nod]=1;
for(p=g[nod]; p!=NULL; p=p->urm)
if(!s[p->nod]) dfs(p->nod);
postordine[++nr]=nod;
}
void dfst(int nod)
{
lista *p;
s[nod]=0;
for(p=gt[nod]; p!=NULL; p=p->urm)
if(s[p->nod]) dfst(p->nod);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(; m>0 ;m--)
{
scanf("%d%d",&i,&j);
p=new lista;
p->nod=j;
p->urm=g[i];
g[i]=p;
p=new lista;
p->nod=i;
p->urm=gt[j];
gt[j]=p;
}
for(i=1; i<=n; i++)
if(!s[i]) dfs(i);
for(i=n; i>0; i--)
if(s[postordine[i]])
{
++nrcp;
dfst(postordine[i]);
}
printf("%d",nrcp);
return 0;
}