Pagini recente » Cod sursa (job #1549627) | Cod sursa (job #96075) | Cod sursa (job #1776665) | Cod sursa (job #2171118) | Cod sursa (job #410170)
Cod sursa(job #410170)
#include<stdio.h>
#define nmax 10000
int n,m,x,y,a[nmax][nmax],b[nmax][nmax],viz[nmax],viz2[nmax];
int i,j,p,u,z,c[nmax],ok,nr;
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d", &n, &m);
for(j=1;j<=m;j++)
{
scanf("%d %d", &x, &y);
a[x][0]++;
a[x][a[x][0]]=y;
b[y][0]++;
b[y][b[y][0]]=x;
}
for(i=1;i<=n;i++)
if(!viz[i])
{
p=1;
u=1;
viz[i]=1;
c[1]=i;
while(p<=u)
{
y=c[p];
for(i=1;i<=a[y][0];i++)
{
z=a[y][i];
if(viz[z]==0){
u++;
c[u]=z;
viz[z]=1;
}
}
p++;
}
p=1;
u=1;
viz2[i]=1;
c[1]=i;
while(p<=u)
{
y=c[p];
for(i=1;i<=b[y][0];i++)
{
z=b[y][i];
if(viz2[z]==0){
u++;
c[u]=z;
viz2[z]=1;
}
}
p++;
}
for(i=1;i<=n;i++)
if(viz[i] && viz2[i]){
viz[i]=viz2[i]=-1;
}
else if(viz[i] || viz2[i]){
viz[i]=viz2[i]=0;
}
nr++;
}
printf("%d", nr);
return 0;
}