Cod sursa(job #771763)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 26 iulie 2012 22:39:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
using namespace std;

int n,m,i;
struct lista
{int nod;
 lista* next;};
lista* a[100001];

void add(int x, int y)
{lista* q = new lista;
 q->nod=y;
 q->next=a[x];
 a[x]=q;}

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

int viz[100001], nrconex;

void depth(int e)
{lista* q=a[e];
while(q)
   {if(viz[q->nod]==0)
       {viz[q->nod]=nrconex;
       depth(q->nod);}
    q=q->next;}
}

int main()
{f>>n>>m;
int x,y;
for( i=1; i<=m; i++)
  {f>>x>>y;
  add(x,y);
  add(y,x);}
  
nrconex=0;

for(i=1; i<=n; i++)
    if(viz[i]==0)
     {viz[i]=nrconex; 
      nrconex++;       
      depth(i);}  
  
g<<nrconex;
f.close();
g.close();
return 0;}