Pagini recente » Cod sursa (job #65158) | Cod sursa (job #1370359) | Cod sursa (job #2275814) | Cod sursa (job #2418025) | Cod sursa (job #2653630)
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;
uint dfs(vector<vector<uint>> &edges)
{
size_t N = edges.size();
vector<bool> visited(N, false);
stack<uint> S;
uint comps = 0;
for (size_t i = 0; i < N; i++)
{
if (!visited[i])
{
S.push(i);
comps++;
while (!S.empty())
{
uint v = S.top();
S.pop();
if (!visited[v])
{
visited[v] = true;
for (uint w : edges[v])
{
S.push(w);
}
}
}
}
}
return comps;
}
int main(int argc, char const *argv[])
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
uint N, M;
fin >> N >> M;
vector<vector<uint>> edges(N);
for (uint i = 0; i < M; i++)
{
uint x, y;
fin >> x >> y;
edges[x-1].push_back(y-1);
edges[y-1].push_back(x-1);
}
fout << dfs(edges);
return 0;
}