Pagini recente » Cod sursa (job #2953488) | Cod sursa (job #1440460) | Cod sursa (job #1883675) | Cod sursa (job #1553462) | Cod sursa (job #1368911)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
vector<int>* Graph;
bool* beenHere;
void addToStack(stack<int>* dest, int source)
{
dest->push(source);
beenHere[source] = true;
}
void DFS(int x)
{
stack<int> Stiva;
addToStack(&Stiva, x);
while (!Stiva.empty())
{
vector<int>::iterator st = Graph[Stiva.top()].begin();
vector<int>::iterator end = Graph[Stiva.top()].end();
unsigned int capacity = Stiva.size();
for (st; st != end; ++st)
if (!beenHere[*st])
addToStack(&Stiva, *st);
if (capacity == Stiva.size())
Stiva.pop();
}
}
int main()
{
ifstream in("dfs.in");
ofstream out("dfs.out");
int Noduri;
int Muchii;
int a;
int b;
int i;
int CompCnx = 0;
in >> Noduri >> Muchii;
Graph = new vector<int>[Noduri + 1];
beenHere = new bool[Noduri + 1];
memset(beenHere, 0, sizeof(bool) * (Noduri + 1));
for (i = 0; i != Muchii; ++i)
{
in >> a >> b;
Graph[a].push_back(b);
Graph[b].push_back(a);
}
in.close();
for (i = 1; i <= Noduri; ++i)
if (!beenHere[i])
{
++CompCnx;
DFS(i);
}
out << CompCnx;
out.close();
delete[] Graph;
delete[] beenHere;
return 0;
}