Cod sursa(job #745131)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 10 mai 2012 16:23:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb

#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;
	
}