Pagini recente » Cod sursa (job #1909009) | Borderou de evaluare (job #1170468) | Cod sursa (job #1920648) | Cod sursa (job #2403341) | Cod sursa (job #2433009)
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;
typedef vector<vector<int>> matrix_type;
set<int> vizitate;
int n_conexe = 0;
int dump(matrix_type& m, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%d ", m[i][j]);
printf("\n");
}
return 0;
}
int dfs(int i, matrix_type& m, int n) {
set<int>::iterator it = vizitate.find(i);
if (it != vizitate.end())
return 0;
vizitate.insert(i);
for (int j = 0; j < n; j++) {
if (m[i][j])
dfs(j, m, n);
}
return 0;
}
int main() {
fstream fin("dfs.in", ios::in);
fstream fout("dfs.out", ios::out);
int N, M;
// citesc N M
fin >> N >> M;
// definesc graful
matrix_type graf(N, vector<int>(N, 0) );
for (int i = 0; i < M; i++) {
int lin, col;
fin >> lin >> col;
graf[lin - 1][col - 1] = 1;
graf[col - 1][lin - 1] = 1;
}
//
for (int i = 0; i < N; i++) {
set<int>::iterator it = vizitate.find(i);
if (it == vizitate.end())
n_conexe++;
dfs(i, graf, N);
}
//dump(graf, N);
// scriu rezultatul
fout << n_conexe;
//cout << n_conexe << endl;
// the end
fin.close();
fout.close();
return 0;
}