Pagini recente » Cod sursa (job #1571673) | Cod sursa (job #3304339) | Cod sursa (job #443470) | Cod sursa (job #3334563) | Cod sursa (job #2429630)
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 100002;
stack <int> s;
vector <int> v[2*NMAX];
bool vizitat[NMAX]={0};
int N, M;
void citire()
{
ifstream f("dfs.in");
f>>N>>M;
int n1, n2;
for (int i=0; i<M; i++)
{
f>>n1>>n2;
v[n1].push_back(n2);
v[n2].push_back(n1);
}
}
void afisare(int componenteConexe)
{
ofstream g("dfs.out");
g<<componenteConexe;
}
void dfs(int nod)
{
int nodCurent,next;
nodCurent=nod;
if(!s.empty())
{
vizitat[nodCurent]=true;
bool ok=false;
for (int i=0; i<v[nodCurent].size(); i++)
{
next=v[nodCurent][i];
if (vizitat[next]==false)
{
s.push(next);
ok=true;
break;
}
}
if (ok)
dfs(next); else
{
s.pop();
if (!s.empty())
{
next=s.top();
dfs(next);
}
}
}
}
int main()
{
int componenteConexe=0;
citire();
for (int i=1; i<=N; i++)
if (!vizitat[i])
{
s.push(i);
dfs(i);
componenteConexe++;
}
afisare(componenteConexe);
return 0;
}