Pagini recente » Cod sursa (job #2867878) | Cod sursa (job #1459138) | Cod sursa (job #2408619) | Cod sursa (job #899954) | Cod sursa (job #1641064)
// Infoarena DFS
#include <fstream>
#include <vector>
#include <stack>
typedef unsigned int uint;
std::vector<std::vector<uint>> graph;
uint vertices, edges;
void read()
{
std::ifstream f("dfs.in");
f >> vertices >> edges;
graph.resize(n);
for (uint i = 0; i < edges; i++)
{
uint x, y;
f >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
}
std::vector<uint> depthFirstSearch(uint vertex)
{
if (!isValidVertex(vertex))
return std::vector<uint>();
std::vector<bool> visited(vertices);
std::stack<uint> stack;
std::vector<uint> connectedComponent;
stack.push(vertex);
visited[vertex] = true;
connectedComponent.push_back(vertex);
while (!stack.empty())
{
uint index, element = stack.top();
bool found = false;
for (index = 0; index < getDegree(element) && !found; index++)
if (!visited[graph[element][index]])
found = true;
if (found)
{
index--;
stack.push(graph[element][index]);
visited[graph[element][index]] = true;
connectedComponent.push_back(graph[element][index]);
}
else
stack.pop();
}
return connectedComponent;
}
std::vector<std::vector<uint>> getConnectedComponents()
{
std::vector<std::vector<uint>> connectedComponents;
std::vector<bool> visited(vertices, false);
for (uint i = 0; i < vertices; i++)
{
if (!visited[i])
{
connectedComponents.push_back(depthFirstSearch(i));
for (uint j = 0; j < connectedComponents.back().size(); j++)
visited[connectedComponents.back()[j]] = true;
}
}
return connectedComponents;
}
int main()
{
read(n, m, graph);
std::vector<std::vector<uint>> cC = getConnectedComponents();
std::ofstream g("dfs.out");
g << cC.size();
return 0;
}