Pagini recente » Cod sursa (job #2820179) | Cod sursa (job #683740) | Cod sursa (job #261794) | Cod sursa (job #1997924) | Cod sursa (job #1699054)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
const int NMax = 1000001;
int visited[NMax];
vector<int> graf[NMax];
void DFS(int nod, int visited[NMax]) {
int idNeighbour;
int nrNeighbours = graf[nod].size();
visited[nod] = 1;
for (int i = 0; i < nrNeighbours; i++) {
idNeighbour = graf[nod][i];
if (visited[idNeighbour] != 1) {
DFS(idNeighbour, visited);
}
}
}
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);
}
memset(visited, 0, sizeof(visited));
nrComponente = 0;
for (int i = 0; i < N; i++) {
if (visited[i] == 0) {
DFS(i, visited);
nrComponente++;
}
}
fout << nrComponente;
return 0;
}