Cod sursa(job #1965890)

Utilizator SirbuSirbu Ioan Sirbu Data 14 aprilie 2017 18:21:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

vector < int > graf[100002];
bool viz[100002];


void DFS (int nod){

  viz[nod] = true;
  vector < int > ::iterator it;
  for (it = graf[nod].begin(); it != graf[nod].end(); ++it)
    if (viz[*it] == false)
      DFS(*it);
}


int main()
{
    int n,m,x,y;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i){
      fin >> x >> y;
      graf[x].push_back(y);
      graf[y].push_back(x);
    }

    int comp = 0;
    for (int i = 1; i <= n; ++i){
      if (viz[i] == false){
          comp++;
          DFS(i);
      }
    }

    fout << comp << "\n";
    return 0;
}