Pagini recente » Cod sursa (job #3226451) | Cod sursa (job #1177627) | Cod sursa (job #986758) | Cod sursa (job #536910) | Cod sursa (job #2773198)
#include <fstream>
#include <vector>
const int MAX_N = 100001;
const int MAX_M = 200001;
int n, m;
int components = 0;
bool flag[MAX_M] = { 0 };
std::vector<int> graph[MAX_N];
void read()
{
std::ifstream input("dfs.in");
input >> n >> m;
int x, y;
for (int count(0); count < m; ++count) {
input >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
input.close();
}
void print()
{
std::ofstream output("dfs.out");
output << components << '\n';
output.close();
}
void dfs(int vertex)
{
flag[vertex] = true;
for (auto neighbor : graph[vertex]) {
if (!flag[neighbor]) {
dfs(neighbor);
}
}
}
void connected_components()
{
for (int vertex(1); vertex <= n; ++vertex) {
if (!flag[vertex]) {
++components;
dfs(vertex);
}
}
}
int main()
{
read();
connected_components();
print();
return 0;
}