Cod sursa(job #771761)

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

int n,m,gata,gasit;
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 i,viz[100001], stack[100001], end, nrconex,s;

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;

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