Pagini recente » Cod sursa (job #2499949) | Cod sursa (job #1578842) | Cod sursa (job #3211639) | Cod sursa (job #2591321) | Cod sursa (job #1368896)
#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();
bool added = false;
for (st; st != end; ++st)
if (!beenHere[*st])
{
addToStack(&Stiva, *st);
added = true;
}
//if (!added)
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;
}