Pagini recente » Cod sursa (job #2419686) | Cod sursa (job #1258780) | Cod sursa (job #3041132) | Cod sursa (job #1009296) | Cod sursa (job #2831424)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
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)
{
bool* visited = new bool[adj.size()];
memset(visited, 0, adj.size());
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;
}