Cod sursa(job #149044)

Utilizator mariaciPopa Marius Ionut mariaci Data 5 martie 2008 11:27:57
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
int n,m,a[50000][50000],viz[50000],nc;
void parc(int v)
{ int i,p,u,c[50000],vf;
  p=u=1;
  c[p]=v;
  viz[v]=nc;
  while(p<=u)
     { vf=c[p];
       p++;
       for(i=1;i<=n;i++)
	  if(a[vf][i] && !viz[i])
	    { u++;
	      c[u]=i;
	      viz[i]=nc;
	    }
     }
}
void conex()
{ int ok=1,i;
  nc=1;
  parc(1);
  while(ok)
     { for(i=1;i<=n;i++)
	   if(viz[i]==0) break;
       if(i<=n)
	  { nc++;
	    parc(i);
	  }
       else ok=0;
     }
  printf("%d\n",nc);
}
int main()
{ freopen("dfs.in","r",stdin);
  freopen("dfs.out","w",stdout);
  scanf("%d%d",&n,&m);
  int x,y,i;
  for(i=1;i<=m;i++)
     { scanf("%d%d",&x,&y);
       a[x][y]=a[y][x]=1;
     }
  conex();
  return 0;
}