Pagini recente » Istoria paginii utilizator/smoke12345 | Istoria paginii utilizator/robert_07t | Concursuri Virtuale | Statistici Schipor Daniel (dschipor) | Cod sursa (job #1699056)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
const int NMax = 1000001;
bool visited[NMax];
vector<int> graf[NMax];
void DFS(int nod) {
visited[nod] = true;
int nrVecini = graf[nod].size();
for (int i = 0; i < nrVecini; i++) {
if (!visited[graf[nod][i]]) {
DFS(graf[nod][i]);
}
}
}
int main() {
int N, M, x, y, nrComponente;
nrComponente = 0;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
fin >> N >> M;
for (int i = 0; i < M; i++) {
fin >> x >> y;
graf[x - 1].push_back(y - 1);
graf[y - 1].push_back(x - 1);
}
nrComponente = 0;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
DFS(i);
nrComponente++;
}
}
fout << nrComponente;
return 0;
}