Pagini recente » Cod sursa (job #1660401) | Cod sursa (job #31368) | Cod sursa (job #545565) | Cod sursa (job #829427) | Cod sursa (job #745131)
Cod sursa(job #745131)
#include <cstdio>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
#define f first
#define s second
#define mp make_pair
#define pb push_back
const int N=100001;
bitset<N> uz;
vector<int> G[N];
stack<pair<int,size_t> > S;
int n,m,sol;
void read ()
{
ifstream in ("dfs.in");
in>>n>>m;
for(int x,y;m;--m)
{
in>>x>>y;
G[x].pb(y);
G[y].pb(x);
}
}
void DFS ()
{
for(;S.size();)
{
int nd=S.top().f;
size_t i=S.top().s;
for(;i<G[nd].size();++i)
if(!uz[G[nd][i]])
{
uz[G[nd][i]]=1;
break;
}
if(i<G[nd].size())
{
S.top().s=i;
S.push(mp(G[nd][i],0));
}
else
S.pop();
}
}
void solve ()
{
for(int i=1;i<=n;++i)
if(!uz[i])
{
++sol;
uz[i]=1;
S.push(mp(i,0));
DFS ();
}
}
void out ()
{
freopen ("dfs.out","w",stdout);
printf("%d",sol);
}
int main ()
{
read ();
solve ();
out ();
return 0;
}