Pagini recente » Borderou de evaluare (job #3329902) | Cod sursa (job #530653) | Cod sursa (job #3316936) | Cod sursa (job #3318819) | Cod sursa (job #3335785)
#include <bits/stdc++.h>
using data = unsigned int;
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
void dfsProcedure(data node, std::vector<std::vector<data>>& graph, std::vector<char>& hasBeenVisited)
{
hasBeenVisited[node] = true;
for (data neighbour : graph[node])
if (!hasBeenVisited[neighbour])
dfsProcedure(neighbour, graph, hasBeenVisited);
}
int main()
{
data nodeNum, edgeNum, x, y, connectedComps;
fin >> nodeNum >> edgeNum;
std::vector<std::vector<data>> graph(nodeNum + 1);
std::vector<char> hasBeenVisited(nodeNum + 1, false);
while (fin >> x >> y)
{
graph[x].push_back(y);
graph[y].push_back(x);
}
for (size_t node = 1 ; node < hasBeenVisited.size(); ++node)
if (!hasBeenVisited[node])
{
dfsProcedure(node, graph, hasBeenVisited);
connectedComps += 1;
}
fout<<connectedComps;
return 0;
}