Pagini recente » Cod sursa (job #913061) | Cod sursa (job #495648) | Cod sursa (job #2298018) | Cod sursa (job #386152) | Cod sursa (job #489044)
Cod sursa(job #489044)
// http://infoarena.ro/problema/dfs
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
int nodes,edges,conexComponents;
vector< list<int> > graph;
vector<bool> visited;
void read();
void depthFirst(int startNode);
void write();
int main() {
read();
for(int i=1;i<=nodes;i++)
if(!visited.at(i)) {
depthFirst(i);
conexComponents++;
}
write();
return (0);
}
void read() {
ifstream in("dfs.in");
int from,to;
in >> nodes >> edges;
graph.resize(nodes+1);
visited.resize(nodes+1);
for(int i=1;i<=edges;i++) {
in >> from >> to;
graph.at(from).push_back(to);
graph.at(to).push_back(from);
}
in.close();
}
void depthFirst(int toVisit) {
visited.at(toVisit) = true;
for(list<int>::iterator it=graph.at(toVisit).begin();it!=graph.at(toVisit).end();it++)
if(!visited.at(*it))
depthFirst(*it);
}
void write() {
ofstream out("dfs.out");
out << conexComponents << "\n";
out.close();
}