Cod sursa(job #2217601)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 1 iulie 2018 01:13:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
/**
  *  Worg
  */
#include <cstdio>
#include <vector>

FILE *fin = freopen("dfs.in", "r", stdin); FILE *fout = freopen("dfs.out", "w", stdout);

/*-------- Data --------*/
int n, m;
std::vector<std::vector<int > > graph;

std::vector<int > seen;
/*-------- --------*/

void ReadInput() {
  scanf("%d%d", &n, &m); graph.resize(n + 1);
  for(int i = 0; i < m; i++) {
    int u, v; scanf("%d%d", &u, &v);

    graph[u].push_back(v); graph[v].push_back(u);
  }
}

void DFS(int node) {
  seen[node] = true;
  for(auto& itr : graph[node]) {
    if(seen[itr]) continue;

    DFS(itr);
  }
}

int CountComponents() {
  int componentCount = 0;

  seen = std::vector<int >(n + 1, false);

  for(int i = 1; i <= n; i++) {
    if(!seen[i]) {
      componentCount++;
      DFS(i);
    }
  }

  return componentCount;
}

int main() {
  ReadInput();

  printf("%d\n", CountComponents());

  return 0;
}