Pagini recente » Cod sursa (job #2090767) | Cod sursa (job #2569562) | Cod sursa (job #439538) | Istoria paginii runda/wellcodesimulareclasa11-12-11martie | Cod sursa (job #1762577)
#include <fstream>
#include <vector>
#include <stack>
class SimpleGraph
{
int mSize;
std::vector<int> *edges;
public:
SimpleGraph(int size)
{
mSize = size + 1;
edges = new std::vector<int>[mSize];
}
void addEdge(int a, int b)
{
edges[a].push_back(b);
edges[b].push_back(a);
}
int countConextComponents()
{
int counter = 0;
bool *is_visited;
is_visited = new bool[mSize];
for (int i = 0; i < mSize; ++i) is_visited[i] = false;
std::stack<int> dfs_stack;
for (int i = 1; i < mSize; ++i) {
if (!is_visited[i]) {
++counter;
dfs_stack.push(i);
is_visited[i] = true;
while (!dfs_stack.empty()) {
int current_vertex = dfs_stack.top();
dfs_stack.pop();
for (int vertex : edges[current_vertex]) {
if (!is_visited[vertex]) {
dfs_stack.push(vertex);
is_visited[vertex] = true;
}
}
}
}
}
return counter;
}
};
int main()
{
std::ifstream input("dfs.in");
std::ofstream output("dfs.out");
int n, m;
input >> n >> m;
SimpleGraph graph(n);
for (int i = 0; i < m; ++i) {
int a, b;
input >> a >> b;
graph.addEdge(a, b);
}
output << graph.countConextComponents() << '\n';
return 0;
}