Cod sursa(job #356083)

Utilizator yonutzTalos Ionut yonutz Data 13 octombrie 2009 14:27:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream.h>
#include <iostream.h>
#include <stdio.h>

using namespace std;
long i,comp_conex=0;
long n,m,vizitat[100005];
typedef struct nod




{
    int info;
    nod *urm;
} *pNod;
pNod v[100005];
 void citire()
{int i,j,k,x,y;
 ifstream f("dfs.in");
 f>>n>>m;
 pNod nou;
 for (i = 1; i <= m; i++)
  
  
  
  
    {
     f>>x>>y;
        nou=new nod;
        nou->info=x;
        nou->urm=v[y];
        v[y]=nou;
        nou=new nod;
        nou->info=y;
        nou->urm=v[x];
        v[x]=nou;
    }
    f.close();
}





void df(int nod)
{pNod p;
    vizitat[nod] = 1;
    for (p=v[nod];p!=NULL;p=p->urm) if(!vizitat[p->info]) df(p->info);
}
void afisare()
{ofstream g("dfs.out");
g<<comp_conex;
g.close();
}




int main()
{int j,k,indice=1;
 citire();
 
while(indice!=0)
{indice=0;
for(k=1;k<=n;k++)
  if(vizitat[k]==0)
  {indice=1;comp_conex++;df(k);}
}
afisare();
return 0;
}