Cod sursa(job #1180289)

Utilizator abel1090Abel Putovits abel1090 Data 30 aprilie 2014 13:47:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
///DFS
#include<fstream>
#include<vector>
#include<list>
#include<stack>

using namespace std;

class Graph {

private:
    vector<list<unsigned> > adjList;
    unsigned numNodes, numArcs;
public:
    Graph(ifstream &);
    unsigned getNumConComp(); ///DFS

};

Graph::Graph(ifstream &inStr) {
    inStr >> numNodes >> numArcs;

    adjList.resize(numNodes);

    unsigned from, to;
    for(unsigned i=0; i<numArcs; i++) {
        inStr >> from >> to;
        adjList[from-1].push_back(to-1);
        adjList[to-1].push_back(from-1);
    }
}

unsigned Graph::getNumConComp() {
    unsigned numConComp = 0;
    vector<bool> seen(numNodes, false);

    list<unsigned>::iterator it;
    unsigned current;
    for(unsigned i=0; i<numNodes; i++)
        if(!seen[i]) {

            stack<unsigned> s;
            s.push(i);
            while(!s.empty()) {
                current = s.top();
                s.pop();
                if(!seen[current]) {
                    seen[current] = true;
                    for(it=adjList[current].begin(); it!=adjList[current].end(); it++) {
                        s.push(*it);
                    }
                }
            }

            numConComp++;
        }

    return numConComp;
}

int main() {
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");

    Graph graph(fin);
    fout << graph.getNumConComp();

    return 0;
}