Cod sursa(job #1762577)

Utilizator CaterpillerLeaf Caterpiller Caterpiller Data 23 septembrie 2016 19:42:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#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;
}