Cod sursa(job #410166)

Utilizator lovestospoogestan marsh lovestospooge Data 4 martie 2010 10:03:53
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#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;
}