Pagini recente » Cod sursa (job #2789634) | Cod sursa (job #2831672) | Cod sursa (job #40790) | Cod sursa (job #2243937) | Cod sursa (job #270658)
Cod sursa(job #270658)
#include<stdio.h>
#include<string.h>
#define nmax 100001
int n,m,st[nmax],ns,viz[nmax],cont;
struct nod
{
int drum;
nod *urm;
} *l[nmax] , *lt[nmax];
void DF1(int);
void DF2(int);
void add(nod *&inc,int info)
{
nod *p=new nod;
p->drum=info;
p->urm=inc;
inc=p;
}
int main()
{
int a,b;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&a,&b);
add(l[a],b);
add(lt[b],a);
}
for(int i=1;i<=n;++i)
if (!viz[i])
DF1(i);
memset(viz,0,sizeof(viz));
for(int i=n;i;--i)
if (!viz[st[i]])
{
DF2(st[i]);
++cont;
//printf("\n");
}
printf("%d\n",cont);
return 0;
}
void DF1 (int x)
{
nod *p=l[x];
viz[x]=1;
for(;p;p=p->urm)
if (!viz[p->drum])
DF1(p->drum);
st[++ns]=x;
}
void DF2(int x)
{
nod *p=lt[x];
viz[x]=1;
//printf("%d ",x);
for(;p;p=p->urm)
if (!viz[p->drum])
DF2(p->drum);
}