Cod sursa(job #851486)

Utilizator blechereyalBlecher Eyal blechereyal Data 9 ianuarie 2013 23:45:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
using namespace std;
#include <vector>
#include <fstream>

#define max 100002
ifstream f("dfs.in");
ofstream g("dfs.out");
int N,M,X,Y;
int viz[max];
vector <int> graf[max];
 
void DFS(int nod){
unsigned int i;
viz[nod]=1;
vector <int>::iterator it; 
  for (i=0;i<graf[nod].size();i++)
        if (viz[graf[nod][i]]==0)
         DFS(graf[nod][i]);
    
}

int main(){
int i,cnt=0;
f>>N>>M;
for (i=0;i<M;i++){
    f>>X>>Y;
    graf[X].push_back(Y);
    graf[Y].push_back(X);
    }
    

for (i=1;i<=N;++i)
if (viz[i]==0) {DFS(i);cnt++;}
g<<cnt;   
return 0;
}