Pagini recente » Cod sursa (job #1157553) | Cod sursa (job #1177236) | Cod sursa (job #2606134)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
#define NMAX 100009
class Task {
std::vector<int> matrix[NMAX];
size_t N;
size_t M;
void read_input() {
std::ifstream in("dfs.in");
in >> N;
in >> M;
for (size_t i = 0; i < M; i++) {
int x;
int y;
in >> x;
in >> y;
matrix[x].push_back(y);
matrix[y].push_back(x);
}
in.close();
}
void show_matrix() {
for (int i = 1; i <= N; i++) {
std::cout<<i<<":";
for (int j = 0; j < matrix[i].size(); j++) {
std::cout<<matrix[i][j]<<" ";
}
std::cout<<"\n";
}
}
void DFS_UTIL(int node, std::vector<int> &visited) {
visited[node] = 1;
for (auto const &x: matrix[node]) {
if (!visited[x]) {
DFS_UTIL(x, visited);
}
}
}
int DFS() {
std::vector<int> visited(N + 1, 0);
int conex = 0;
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
DFS_UTIL(i, visited);
conex++;
}
}
return conex;
}
void print(int res) {
std::ofstream out("dfs.out");
out<<res<<"\n";
out.close();
return;
}
public:
void solve() {
read_input();
print(DFS());
}
};
int main() {
Task* task = new Task();
task->solve();
delete task;
return 0;
}