Pagini recente » Cod sursa (job #2188698) | Cod sursa (job #2464748) | Cod sursa (job #1279342) | Cod sursa (job #282615) | Cod sursa (job #2723566)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
// numarul maxim de noduri
const int Nmax = 100005;
vector<int> graph[Nmax];
bool visited[Nmax];
void dfs(int node) {
visited[node] = true;
// parcurg toti vecinii y ai lui node
for (int i = 0; i < graph[node].size(); i++) {
int y = graph[node][i];
if (!visited[y]) {
dfs(y);
}
}
}
int main()
{
int N, M, x, y, i;
in >> N >> M;
for (int i = 0; i < M; i++) {
in >> x >> y;
graph[x].push_back(y); // adaug in lista vecinilor lui x pe y
graph[y].push_back(x); // adaug in lista vecinilor lui y pe x
}
// afisare lista vecini
// for (int node = 1; node <= N; node++) {
// out << node << ": ";
// // parcurg toti vecinii lui node
// for (int y = 0; y < graph[node].size(); y++) {
// out << graph[node][y] << " ";
// }
// out << '\n';
// }
int nr = 0;
for (i = 1; i <= N; i++) {
if (!visited[i]) {
nr++;
dfs(i);
}
}
out << nr << '\n';
return 0;
}