Pagini recente » Cod sursa (job #69650) | Cod sursa (job #2633307) | Cod sursa (job #2128436) | Cod sursa (job #1964138) | Cod sursa (job #741295)
Cod sursa(job #741295)
#include <fstream>
#include <iostream>
#include <list>
#include <vector>
typedef std::list<unsigned int> adiacent;
typedef std::vector<adiacent> nod;
nod graf;
bool *mark;
void DepthFirstSearch (unsigned int nod)
{
mark[nod] = true;
for (adiacent::iterator i(graf[nod].begin()), stop(graf[nod].end()) ; i != stop ; ++i)
{
if (mark[*i])
continue;
DepthFirstSearch(*i);
}
graf[nod].clear();
}
int main (void)
{
unsigned int n,m;
std::ifstream input("dfs.in");
input >> n >> m;
graf.resize(n + 1);
unsigned int x,y;
do
{
input >> x >> y;
graf[x].push_front(y);
graf[y].push_front(x);
--m;
}
while (m);
input.close();
unsigned int counter(0);
mark = new bool [n + 1] ( );
for (unsigned int index(1) ; index <= n ; ++index)
{
if (mark[index])
continue;
++counter;
DepthFirstSearch(index);
}
delete [ ] mark;
std::ofstream output("dfs.out");
output << counter << '\n';
output.close();
return 0;
}