Cod sursa(job #1259579)

Utilizator MONSERDenis Fovas MONSER Data 10 noiembrie 2014 10:49:15
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");

int n, m, i, l, c,nc, nconx;
bool a[2000][2000], v[2000];

void dfs(int x) {
  int i;
  for (i = 1; i <= n; i++)
    if (a[nc][i] and  not v[i]) {
      v[i] = true;
      dfs(i);
    }
}

int main()
{
  fi >> n >> m;
  for (i = 1; i <= m; i++) {
    fi >> l >> c;
    a[l][c] = a[c][l] = true;
  }
  for (i = 1; i <= n; i++) {
    if(not v[i]) {
      v[i] = true;
      nconx++;
      nc++;
      dfs(i);
    }
  }
  fo<<nconx;
  return 0;
}