Cod sursa(job #280512)

Utilizator sticksuTihu Mircea sticksu Data 13 martie 2009 13:43:12
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream.h>

ifstream f("dfs.in");
ofstream g("dfs.out");

int a[10000][10000],viz[10000000],c[10000000];

unsigned long n,q;

unsigned long parcurgere(unsigned long x,unsigned long m)
{
 unsigned long p=1,u=1,i;
 viz[x]=m;
 c[u]=x;
 while(p<=u)
   {
    for(i=1;i<=n;i++)
       if(a[c[p]][i]==1&&viz[i]==0)
	  {c[++u]=i;
           viz[i]=m;

	  }
    p++;
   }
 return 0;
}

int main()
{unsigned long i,x,y;
 int z=1;
 f>>n>>q;
 for(i=1;i<=q;i++)
    {f>>x>>y; a[x][y]=a[y][x]=1;}
 f.close();
 parcurgere(1,z);
 for(i=1;i<=n;i++)
    if(viz[i]==0) parcurgere(i,z++);

 g<<z-- ;
 g.close();
 return 0;
}