Pagini recente » Cod sursa (job #545931) | Cod sursa (job #1142502) | Cod sursa (job #181276) | Cod sursa (job #63629) | Cod sursa (job #1641104)
// Infoarena DFS
#include <fstream>
#include <vector>
#include <stack>
std::vector<std::vector<int>> graph;
std::vector<bool> visited;
int vertices, edges;
void dfs(int vertex)
{
if (vertex < 0 || vertex > vertices - 1)
return;
std::stack<int> stack;
stack.push(vertex);
visited[vertex] = true;
while (!stack.empty())
{
int index, element = stack.top();
bool found = false;
for (index = 0; index < graph[element].size() && !found; index++)
if (!visited[graph[element][index]])
found = true;
if (found)
{
index--;
stack.push(graph[element][index]);
visited[graph[element][index]] = true;
}
else
stack.pop();
}
}
int main()
{
std::ifstream f("dfs.in");
f >> vertices >> edges;
graph.resize(vertices);
visited.resize(vertices, false);
for (int i = 0; i < edges; i++)
{
int x, y;
f >> x >> y;
x--;
y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
int c = 0;
for (int i = 0; i < visited.size(); i++)
if (!visited[i])
{
dfs(i);
c++;
}
std::ofstream g("dfs.out");
g << c;
return 0;
}