Cod sursa(job #931373)

Utilizator zvonTutuldunsa Voronokda zvon Data 28 martie 2013 10:39:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
vector < vector <int> > b;
bool wiz[100002];

void dfs(int z) {
wiz[z]=1; int k;
while (!b[z].empty()) { k=b[z].back();
b[z].pop_back(); if(!wiz[k]) { dfs(k);}     }
}


int main()
{
int n,m,x,y,num=0;
ifstream sursa("dfs.in");
ofstream dest("dfs.out");
sursa >> n >> m; b.resize(n+1);
for (int i=1; i<=m; i++) { 
  sursa >> x >> y;   b[x].push_back(y);  b[y].push_back(x);  }  
  sursa.close(); 

for (int i=1; i<=n ;i++) { wiz[i]=0;} 

for (int i=1; i<=n; i++) 
{ if (!wiz[i]) { num+=1; dfs(i);}}
dest << num; dest.close(); 

return(0);    
}