Cod sursa(job #2195442)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 16 aprilie 2018 13:33:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100000;

vector <int> gr[NMAX + 1];
int viz[NMAX + 1];

void dfs(int nod) {
  viz[nod] = 1;
  for(unsigned i = 0; i < gr[nod].size(); ++i) {
    int fiu = gr[nod][i];
    if(viz[fiu] == 0) {
      dfs(fiu);
    }
  }
}
int main() {
  FILE *fin, *fout;
  int n, m, i, x, y, nc;
  fin = fopen ("dfs.in", "r");
  fout = fopen ("dfs.out", "w");
  fscanf (fin, "%d%d", &n, &m);
  for(i = 1; i <= m; ++i) {
    fscanf (fin, "%d%d", &x, &y);
    gr[y].push_back(x);
    gr[x].push_back(y);
  }
  nc = 0;
  for(i = 1; i <= n; ++i) {
    if(viz[i] == 0) {
      nc++;
      dfs(i);
    }
  }
  fprintf (fout, "%d", nc);
  return 0;
}