Pagini recente » Cod sursa (job #1561618) | Cod sursa (job #971356) | Cod sursa (job #354019) | Cod sursa (job #1273591) | Cod sursa (job #2676247)
#include<iostream>
#include<fstream>
#include <vector>
using namespace std;
int n, m;
int marked[100005];
std::vector<int> g[100005];
int dfs(int node) {
// std::cout << "Marked node " << node << '\n';
marked[node] = 1;
for (int i = 0; i < g[node].size(); i++) {
int new_node = g[node][i];
if (!marked[new_node])
dfs(new_node);
}
}
int main()
{
ifstream f("DFS.in");
ofstream fout("DFS.out");
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
f>> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
int cont = 0;
for (int i = 1; i <= n; i++)
{
if (!marked[i])
{
dfs(i);
cont++;
}
}
fout<< cont;
return 0;
}