Pagini recente » Cod sursa (job #2050246) | Cod sursa (job #1961429) | Cod sursa (job #2035237) | Cod sursa (job #1138650) | Cod sursa (job #2417838)
#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);
}
}