Cod sursa(job #644366)

Utilizator juniorOvidiu Rosca junior Data 6 decembrie 2011 10:36:51
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>

using namespace std;

int nc, n, m, ni, a[2000][2000], v[2000];

void DF (int nc) {
	int i;

	for (i = 1; i <= n; i++)   // pentru fiecare nod
		if (a[nc][i] && !v[i]) { // i este vecin nevizitat al nodului curent?
			v[i] = 1;              // Marcam i ca fiind vizitat.
			DF(i);                 // Continuam parcurgerea in adancime.
		}
}

int main() {
	int i, x, y;
	ifstream fi("dfs.in");
	ofstream fo("dfs.out");

	fi >> n >> m;
	for (i = 1; i <= m; i++) {
		fi >> x >> y;
		a[x][y] = a[y][x] = 1;
	}
	for (ni = 1; ni <= n; ni++)
	  if (!v[ni]) {
      v[ni] = 1;
      DF(ni);
      nc++;
	  }
  fo << nc;
}