Pagini recente » Cod sursa (job #761880) | Cod sursa (job #363970) | Cod sursa (job #47968) | Cod sursa (job #1896332) | Cod sursa (job #2433020)
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;
vector<vector<int>> graf;
vector<int> vizitate;
int n_conexe = 0;
int N, M;
int dump() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%d ", graf[i][j]);
printf("\n");
}
return 0;
}
int dfs(int i) {
if (vizitate[i])
return 0;
vizitate[i] = 1;;
for (int j = 0; j < N; j++) {
if (graf[i][j])
dfs(j);
}
return 0;
}
int main() {
fstream fin("dfs.in", ios::in);
fstream fout("dfs.out", ios::out);
// citesc N M
fin >> N >> M;
// definesc graful
graf.assign(N, vector<int>(N, 0));
vizitate.assign(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++) {
if (vizitate[i] == 0) {
n_conexe++;
dfs(i);
}
}
//dump(graf, N);
// scriu rezultatul
fout << n_conexe;
//cout << n_conexe << endl;
// the end
fin.close();
fout.close();
return 0;
}