Pagini recente » Cod sursa (job #1276110) | Cod sursa (job #1597987) | Cod sursa (job #787585) | Cod sursa (job #154583) | Cod sursa (job #1126472)
#include <fstream>
#include <vector>
#include <list>
using namespace std;
vector< list<int> > adj;
vector<bool> track;
int nrComp;
void readData(int &, int &);
void DepthFirstSearch(int, int);
void writeData(int);
int main(int argc, char *argv[]) {
int nrVertices, nrEdges;
readData(nrVertices, nrEdges);
writeData(nrVertices);
return 0;
}
void readData(int &nrVertices, int &nrEdges) {
int nodeX, nodeY;
fstream in("dfs.in", ios::in);
in >> nrVertices >> nrEdges;
adj.resize(nrVertices+1);
track.resize(nrVertices+1);
for (int i = 0; i <= nrVertices; ++i) {
track.push_back(false);
}
for (int i = 0; i < nrEdges; ++i) {
in >> nodeX >> nodeY;
adj[nodeX].push_back(nodeY);
adj[nodeY].push_back(nodeX);
}
in.close();
}
void DepthFirstSearch(int node, int nrVertices) {
track[node] = true;
for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it) {
if (!track[*it]) {
DepthFirstSearch(*it, nrVertices);
}
}
}
void writeData(int nrVertices) {
fstream out("dfs.out", ios::out);
for (int i = 1; i <= nrVertices; ++i) {
if (!track[i]) {
nrComp++;
DepthFirstSearch(i, nrVertices);
}
}
out << nrComp++;
out.close();
}