Cod sursa(job #931340)

Utilizator zvonTutuldunsa Voronokda zvon Data 28 martie 2013 10:20:51
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

void modif(bool wiz[]) { wiz[0]=0; }
void dfs(int z, bool wiz[], vector< vector<int> > b) {
wiz[z]=1; int k;
while (!b[z].empty()) { k=b[z].back();
b[z].pop_back(); if(!wiz[k]) { dfs(k, wiz, b);}     }
}


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

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

return(0);    
}