Pagini recente » Cod sursa (job #2156291) | Cod sursa (job #169605) | Cod sursa (job #1977202) | Cod sursa (job #2222823) | Cod sursa (job #3249571)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
void DFSRec(std::vector<std::vector<int>> &adj, std::vector<bool> &visited, int s)
{
visited[s] = true;
for (auto it : adj[s])
if (visited[it] == false)
DFSRec(adj, visited, it);
}
void DFS(std::vector<std::vector<int>> &ad, int start)
{
int comp = 0;
std::vector<bool> visited(ad.size(), false);
for (int i = 1; i < ad.size(); i++)
{
if (visited[i] == false)
{
DFSRec(ad, visited, i);
comp += 1;
}
};
fout << comp;
}
void addEdge(std::vector<std::vector<int>> &ad, int u, int v)
{
ad[u].push_back(v);
ad[v].push_back(u);
}
int main()
{
int muchii, noduri, v, u;
fin >> noduri >> muchii;
std::vector<std::vector<int>> ad(noduri + 1);
for (int i = 0; i < muchii; i++)
{
fin >> u >> v;
addEdge(ad, u, v);
}
DFS(ad, 1);
return 0;
}