Pagini recente » Cod sursa (job #1818081) | Cod sursa (job #496661) | Cod sursa (job #2641714) | Cod sursa (job #1517752) | Cod sursa (job #2783457)
#include <vector>
#include <cstdio>
class Graph
{
public:
Graph(std::size_t nr_noduri, std::vector<std::vector<int>>&& l_adiacenta)
: nr_noduri(nr_noduri)
, l_adiacenta(std::move(l_adiacenta))
{
}
int componente_conexe() const
{
std::vector<bool> visited(nr_noduri + 1, false);
int res = 0;
for(int node = 1; node <= (int)nr_noduri; ++node)
{
if(!visited[node])
{
++res;
DFS(visited, node);
}
}
return res;
}
private:
void DFS(std::vector<bool>& visited, int start) const
{
visited[start] = true;
for(int v : l_adiacenta[start])
{
if(!visited[v])
{
DFS(visited, v);
}
}
}
private:
std::size_t nr_noduri;
std::vector<std::vector<int>> l_adiacenta;
};
int main()
{
std::freopen("dfs.in", "r", stdin);
std::freopen("dfs.out", "w", stdout);
const Graph g = []()
{
int n, m;
std::scanf("%d %d", &n, &m);
std::vector<std::vector<int>> list(n + 1);
for(int i = 0; i < m; ++i)
{
int x, y;
std::scanf("%d %d", &x, &y);
list[x].push_back(y);
list[y].push_back(x);
}
return Graph(n, std::move(list));
}();
std::printf("%d\n", g.componente_conexe());
}