Cod sursa(job #333409)

Utilizator levap1506Gutu Pavel levap1506 Data 22 iulie 2009 16:23:53
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
using namespace std;
int N,M,i,a,b,nr;
char visit[100010];
vector<int> myV[100010];

void proceed(int i){
    visit[i]=1;
    vector<int>::iterator it;
    for (it=myV[i].begin(); it!=myV[i].end(); it++)
    {
        if (!visit[*it])
           proceed(*it);
    }
}

int main () {
    ifstream in;
    ofstream out;
    in.open("tests/grader_test1.in");
    out.open("dfs.out");
    in >> N >> M;
    for (i=0;i<M;i++) {
        in>>a>>b;
        myV[a].push_back(b);
        myV[b].push_back(a);
    }
    for (i=1;i<=N;i++)
      if(!visit[i]) {
          nr++;
          proceed(i);
      }
    out<<nr;
    out.close();
    return 0;
}