Cod sursa(job #1546956)

Utilizator A63N7pTudor Nazarie A63N7p Data 8 decembrie 2015 21:17:30
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <list>

class Graph {
    int V;
    int comp;
    std::list<int> *adj;
    void DFSUtil(int v, bool visited[]);

public:
    Graph(int V);
    int getComp();
    void addEdge(int, int);
    void DFS();
};

Graph::Graph(int V)
{
    this->V = V;
    comp = 0;
    adj = new std::list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
}

void Graph::DFSUtil(int v, bool visited[])
{
    visited[v] = true;

    for (std::list<int>::iterator i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

void Graph::DFS()
{
    bool *visited = new bool[V];
    for (int i = 0; i < V; ++i)
        visited[i] = false;

    for (int i = 0; i < V; ++i)
        if (!visited[i]) {
            DFSUtil(i, visited);
            comp++;
        }
}

int Graph::getComp()
{
    return comp;
}

int main(int argc, char **argv)
{
    std::ifstream input("dfs.in");
    std::ofstream output("dfs.out");
    int N, M;
    input >> N >> M;
    Graph g(N);
    for (int i = 0; i < M; ++i) {
        int x, y;
        input >> x >> y;
        g.addEdge(x, y);
    }
    g.DFS();
    output << g.getComp() << std::endl;
    input.close();
    output.close();
    return 0;
}