Pagini recente » Cod sursa (job #2063268) | Cod sursa (job #405866) | Cod sursa (job #2858258) | Cod sursa (job #2885774) | Cod sursa (job #632760)
Cod sursa(job #632760)
//varianta iterativa
#include <stdio.h>
#include <vector>
#define NMAX 100010
using namespace std;
vector <int> lista[NMAX];
char vizitat[NMAX];
int marime[NMAX];
struct nod{
int vecin, nod;
}stiva[NMAX];
void dfs(int s){
int i;
int vf=0;
vizitat[s]=1;
stiva[vf].nod=s;
stiva[vf].vecin=-1;//incep sa caut vecini de aici
while(vf>=0){
//pun un vecin al varfului stivei in stiva
while((++(stiva[vf].vecin))<marime[stiva[vf].nod]){
if(vizitat[lista[stiva[vf].nod][stiva[vf].vecin]]==0){
vizitat[lista[stiva[vf].nod][stiva[vf].vecin]]=1;
vf++;
stiva[vf].nod=lista[stiva[vf-1].nod][stiva[vf-1].vecin];
stiva[vf].vecin=-1;
}
}
vf--;
}
}
int main(){
int n,m;
int i;
int a,b;
int conex=0;
FILE *fin=fopen("dfs.in","r");
fscanf(fin,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&a,&b);
a--;b--;
lista[a].push_back(b);
marime[a]++;
lista[b].push_back(a);
marime[b]++;
}
fclose(fin);
//lista[i] contine toti vecinii nodului i
for(i=0;i<n;i++){
if(vizitat[i]==0){
//fac o parcurgere pornind de la nodul i
dfs(i);
conex++;
}
}
FILE *fout=fopen("dfs.out","w");
fprintf(fout,"%d\n",conex);
fclose(fout);
return 0;
}