Pagini recente » Cod sursa (job #2549053) | Cod sursa (job #3195266) | Cod sursa (job #710781) | Cod sursa (job #3179474) | Cod sursa (job #2192626)
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream f("DFS.in");
ofstream g("DFS.out");
vector<vector<int>> G;
unsigned int n, a, i, res;
vector<bool> viz;
void rd()
{
int x, y;
f>>n>>a;
viz.resize(n+3);
G.resize(n+3);
while(f>>x>>y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
struct nod
{
int x, j;/// i-ul din for la care am ramas
nod(int nr, int pas)
:x(nr), j(pas){}
};
stack<nod> s;
void DFS(int x)
{
viz[x]=1;
s.push(nod(x, 0));
while(s.size())
{
x=s.top().x;
for(i=s.top().j;i<G[x].size();i++)
if(!viz[G[x][i]])
{
viz[G[x][i]]=1;
s.top().j=i+1;
s.push(nod(G[x][i], 0));
break;
}
if(i>=G[x].size())
s.pop();
}
}
int nxt()
{
for(i=1;i<=n;i++)
if(!viz[i])return i;
return 0;
}
int main()
{
rd();
a=1;
while(a)
{
DFS(a);
a=nxt();
res++;
}
g<<res;
f.close();
g.close();
return 0;
}