Pagini recente » Cod sursa (job #542530) | Cod sursa (job #2052248) | Cod sursa (job #899353) | Cod sursa (job #1448481) | Cod sursa (job #2182562)
#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include <queue>
#include <fstream>
#include <limits>
std::ofstream g("dfs.out");
std::array<std::vector<int>, 100001> graph;
std::vector<bool> visited(100001, false);
// std::vector<bool> isInQueue(100001, false);
// std::queue<int> nextNodes;
int numNodes, numEdges, source;
void ReadGraph()
{
std::ifstream f("dfs.in");
f >> numNodes >> numEdges; // >> source;
int node, neighbour;
for(int i = 1; i <= numEdges; ++i) {
f >> node >> neighbour;
graph[node].emplace_back(neighbour);
graph[neighbour].emplace_back(node);
}
}
//#define BFS_TRAVERSAL
#define DFS_TRAVERSAL
#ifdef BFS_TRAVERSAL
void Traverse()
{
nextNodes.emplace(source);
isInQueue[source] = true;
cost[source] = 0;
while(!nextNodes.empty()) {
const auto& currentNode = nextNodes.front();
for(const auto& neighbour : graph[currentNode]) {
if(cost[currentNode] + 1 < cost[neighbour]) {
cost[neighbour] = cost[currentNode] + 1;
}
if(!visited[neighbour] && !isInQueue[neighbour]) {
nextNodes.emplace(neighbour);
isInQueue[neighbour] = true;
}
}
visited[currentNode] = true;
nextNodes.pop();
}
}
#endif // BFS_TRAVERSAL
#ifdef DFS_TRAVERSAL
void Traverse(int source)
{
visited[source] = true;
for(const auto& neighbour : graph[source])
if(!visited[neighbour])
Traverse(neighbour);
}
#endif // DFS_TRAVERSAL
int main()
{
ReadGraph();
unsigned int cnt = 0;
for(int i = 1; i <= numNodes; ++i) {
if(!visited[i]) {
Traverse(i);
++cnt;
}
}
g << cnt;
return 0;
}