Pagini recente » Cod sursa (job #2889604) | Cod sursa (job #1681833) | Cod sursa (job #2405517) | Cod sursa (job #3033375) | Cod sursa (job #1180289)
///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;
}