Cod sursa(job #838828)

Utilizator FayedStratulat Alexandru Fayed Data 20 decembrie 2012 18:02:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

vector<int> V[100005];
int n,m,x;
int vizitat[100005];

void dfs(int nod){

vizitat[nod] = 1;
    for(vector<int>::iterator it = V[nod].begin();it!=V[nod].end();it++)
        if(!vizitat[(*it)])
            dfs(*it);
}

int main(){

 f >> n >> m;
 int xs,ys;
 for(int i=1;i<=m;i++){

  f >> xs >> ys;
  V[xs].push_back(ys);
  V[ys].push_back(xs);
 }

for(int i = 1;i<=n;i++){

    if(!vizitat[i]){
        ++x;
            dfs(i);
}}

g << x;

f.close();
g.close();
return 0;
}