Cod sursa(job #2417838)

Utilizator frodobiosif aug frodob Data 1 mai 2019 19:52:58
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
using namespace std;
int N, M;
char** matrice;
char* vizitate;
int conexe = 0;
void dfs(int n);
int main() {
	fstream fin("dfs.in", ios::in);
	fstream fout("dfs.out", ios::out);
	int x, y;
	// citesc N,M
	fin >> N >> M;
	// matrice adiacenta
	matrice = new char*[N];
	for (int i = 0; i < N; i++)
		matrice[i] = new char[N];
	// initializare matrice
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			matrice[i][j] = 0;
	// citire matrice
	for (int i = 0; i < M; i++) {
		fin >> x >> y;
		matrice[x - 1][y - 1] = 1;
		matrice[y - 1][x - 1] = 1;
	}
	// alocare/initializare vizitare
	vizitate = new char[N];
	for (int i = 0; i < N; i++)
		vizitate[i] = 0;

	// parcurgere dfs
	for (int i = 0; i < N; i++) {
		if (0 == vizitate[i]) {
			conexe++;
			dfs(i);
		}
	}
    // afisare
	fout << conexe;
	// delete
	for (int i = 0; i < N; i++)
		delete matrice[i];
	delete[] matrice;
	delete[] vizitate;
	// close
	fin.close();
	fout.close();
}
void dfs(int n) {
	vizitate[n] = 1;
	for (int i = 0; i < N; i++) {
		if ( (matrice[n][i] == 1) && (vizitate[i]==0) )
			dfs(i);
	}
}