Cod sursa(job #280486)

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

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

int a[1000][1000],viz[100000],c[100000];

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[x][i]==1&&viz[i]==0)
	  {c[++u]=i;
           viz[i]=m;

	  }
    p++;
   }
 return 1;
}

int main()
{unsigned long i,x,y;
 int z=1;
 f>>n>>q;
 for(i=1;i<=n;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 1;
}