Cod sursa(job #2379673)

Utilizator gabrielsavuSavu Liviu Gabriel gabrielsavu Data 13 martie 2019 21:49:03
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>

class Node {
private:
    std::list<unsigned long> adj;
public:
    std::list<unsigned long> getAdj() {
        return adj;
    }

    void pushAdj(unsigned long a) {
        adj.push_back(a);
    }
};

class Graph {
private:
    unsigned long noNodes;
    Node *nodes;
public:
    Graph(unsigned long noNodes): noNodes(noNodes) {
        nodes = new Node[noNodes];
    }

    void push(unsigned long a, unsigned long b) {
        nodes[a].pushAdj(b);
        nodes[b].pushAdj(a);
    }

    void DFSUtil(unsigned long start, bool visited[]) {
        std::stack<unsigned long> s;
        s.push(start);
        while(!s.empty()) {
            auto node = s.top();
            s.pop();
            visited[node] = true;
            for(auto it : nodes[node].getAdj()) {
                if(!visited[it]) {
                    s.push(it);
                }
            }
        }
    }

    unsigned long connectedComponents() {
        bool *visited = new bool[this->noNodes];
        for(unsigned long i = 0; i < this->noNodes; i++)
            visited[i] = false;

        unsigned long n = 0;

        for (unsigned long i = 0; i < this->noNodes; i++) {
            if (!visited[i]) {
                DFSUtil(i, visited);
                n ++;
            }
        }
        return n;
    }
};

int main() {
    std::ifstream in("dfs.in");
    std::ofstream out("dfs.out");

    unsigned long n, m, a, b;
    in >> n >> m;
    auto G = new Graph(n);
    for (unsigned long i = 0; i < m; i ++) {
        in >> a >> b;
        G->push(a, b);
    }

    out << G->connectedComponents();
    return 0;
}