Pagini recente » Cod sursa (job #2829181) | Cod sursa (job #231452) | Cod sursa (job #2330306) | Cod sursa (job #227436) | Cod sursa (job #2330948)
#include <algorithm>
#include <fstream>
#include <vector>
void dfs(const int source, const std::vector<std::vector<int>> &G, std::vector<bool> &V)
{
V[source] = true;
for (const int u : G[source])
if (!V[u])
dfs(u, G, V);
}
int main()
{
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int n, m;
fin >> n >> m;
std::vector<std::vector<int>> G(n, std::vector<int>());
int u, v;
while (m--)
{
fin >> u >> v;
G[u - 1].push_back(v - 1);
G[v - 1].push_back(u - 1);
}
int components = 0;
std::vector<bool> V(G.size(), false);
for (int source = 0; source < G.size(); ++source)
if (!V[source])
{
dfs(source, G, V);
components++;
}
fout << components << std::endl;
return 0;
}