Pagini recente » Cod sursa (job #1694476) | Cod sursa (job #676841) | Autentificare | Cod sursa (job #1337255) | Cod sursa (job #3150885)
#include <vector>
#include <fstream>
using namespace std;
void dfs(int node, vector<vector<int>> &edges, vector<int> &parent) {
for (auto &child : edges[node]) {
if (parent[child] != -1) {
parent[child] = node;
dfs(child, edges, parent);
}
}
}
int main() {
int N, M;
ofstream fout("dfs.out");
ifstream fin("dfs.in");
fin >> N >> M;
vector<vector<int>> edges(N, vector<int>(N, 0));
vector<int> parent(N, -1);
for (int i = 0; i < M; i++) {
int x, y;
fin >> x >> y;
edges[x].push_back(y);
edges[y].push_back(x);
}
int comp = 0;
for (int i = 0; i < N; i++) {
if (parent[i] == -1) {
dfs(i, edges, parent);
comp++;
}
}
fout << comp;
fin.close();
fout.close();
return 0;
}