Cod sursa(job #2427319)

Utilizator gabrielsavuSavu Liviu Gabriel gabrielsavu Data 31 mai 2019 16:06:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>

using namespace std;

class Link {
private:
    unsigned from;
    unsigned to;
public:
    Link(unsigned from, unsigned to): from(from), to(to) {}
    unsigned getTo() {
        return this->to;
    }

};


class Graph {
private:
    unsigned V;
    std::list<Link> *adj;

    void DFSUtil(unsigned start, bool *visited) {
        std::stack<unsigned> s;
        s.push(start);

        while(!s.empty()) {
            unsigned v = s.top();
            s.pop();
            if(!visited[v]) {
                visited[v] = true;
                for(auto it : adj[v])
                    s.push(it.getTo());
            }
        }
    }

public:
    Graph(unsigned V): V(V) {
        adj = new std::list<Link>[V + 1];
    }

    void addEdge(unsigned from, unsigned to) {
        Link first_link(from, to);
        Link second_link(to, from);
        adj[from].push_back(first_link);
        adj[to].push_back(second_link);
    }

    void printGraph() {
        for(unsigned i = 1; i <= this->V; i ++) {
            for(auto it : adj[i]) {
                std::cout << "nodul " << i << " este conectat cu " << it.getTo() << std::endl;
            }
        }
    }

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

        unsigned long n = 0;
        for (unsigned long i = 1; i <= this->V; 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->addEdge(a, b);
    }
    out << G->connectedComponents();
    return 0;
}