Pagini recente » Cod sursa (job #2157009) | Cod sursa (job #595238) | Istoria paginii runda/luca_oji3 | Cod sursa (job #814344) | Cod sursa (job #2831427)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
bool visited[100000];
void dfs(int i, bool* visited, std::vector<std::vector<int>> &adj)
{
visited[i] = true;
for (int u : adj[i])
{
if (!visited[u])
{
dfs(u, visited, adj);
}
}
}
int solve(std::vector<std::vector<int>> &adj)
{
int count = 0;
for (int i = 1; i < adj.size(); i++)
{
if (!visited[i])
{
dfs(i, visited, adj);
count = count + 1;
}
}
return count;
}
int main()
{
std::ifstream in;
in.open("dfs.in");
int n, m;
in >> n;
in >> m;
std::vector<std::vector<int>> adj(n + 1);
for (int i = 1; i <= m; i++)
{
int n1, n2;
in >> n1;
in >> n2;
adj[n1].push_back(n2);
adj[n2].push_back(n1);
}
in.close();
/*
for (int i = 1; i <= n; i++)
{
std::cout << i << " ";
for (int v : graph[i])
{
std::cout << v << " ";
}
std::cout << std::endl;
}
*/
std::ofstream of;
of.open("dfs.out");
of << solve(adj) << std::endl;
}