Cod sursa(job #1574769)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 20 ianuarie 2016 20:24:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#define nmax 100050
#include <vector>

using namespace std;

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

bool  v[nmax];
int N, M, compCon;
vector <int> a[nmax];

void del(int x){

    v[x] = true;
  for(int j = 0; j < a[x].size(); ++j){
    if(! v[a[x][j]]){
        del(a[x][j]);
    }
  }
}

int main()
{int x, y, i;
    f>>N>>M;
    for(i = 1; i <= M; ++i){
        f>>x>>y;
       a[x].push_back(y);
       a[y].push_back(x);
    }

    for(i = 1; i <= N; ++i){
      if(!v[i]){
        ++compCon;
        del(i);
      }
    }
    g<<compCon<<'\n';
    return 0;
}