Pagini recente » Cod sursa (job #819224) | Istoria paginii runda/marcel001 | Rating Zachman-Tisca Roxana (ztr535) | Cod sursa (job #1991871) | Cod sursa (job #1699057)
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <string.h>
using namespace std;
const int NMax = 100010;
bool visited[NMax];
vector<int> graf[NMax];
void DFS(int nod) {
visited[nod] = true;
int nrNeighbours = graf[nod].size();
for (int i = 0; i < nrNeighbours; 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;
}