Pagini recente » Cod sursa (job #173105) | Cod sursa (job #903909) | Cod sursa (job #574143) | Cod sursa (job #2319216) | Cod sursa (job #2451475)
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(100001, vector<int>());
int N, M, answer;
void read_from_file(string const& file_path)
{
ifstream fin{file_path};
fin >> N >> M;
int x, y;
for(int i = 1; i <= M; i++)
{
fin >> x >> y;
graph.at(x).push_back(y);
graph.at(y).push_back(x);
}
}
void print_to_file(string const& file_path)
{
ofstream fout{file_path};
fout << answer;
}
void dfs(int node, vector<bool>& visited)
{
visited.at(node) = true;
for(auto& elem : graph.at(node))
{
if(visited.at(elem) == false) dfs(elem, visited);
}
}
void solve()
{
answer = 0;
vector<bool> visited(100001, false);
for(int i = 1; i <= N; i++)
{
if(visited.at(i) == false)
{
answer++;
dfs(i, visited);
}
}
}
int main()
{
read_from_file("dfs.in");
solve();
print_to_file("dfs.out");
}