Cod sursa(job #534745)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 16 februarie 2011 10:05:58
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<vector>
#include<bitset>
#include<queue>
#include<algorithm>

using namespace std ;

#define pb push_back
#define dim 100002

queue<int> q;
int x,nr,n,m;
bitset<dim> viz;
vector <int> v[dim];

inline void add(int x , int y)
{ 
	v[x].pb(y); 
}
void read() 
{
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=1 ; i<=n;i++)
	{
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
}
void solve () 
{
	for(int i=1 ; i<=n ; i++)
	{
		if ( viz[i] == 0 )
		{
			nr++;
			viz[i] = 1; 
			for(q.push ( i ) ; !q.empty() ; q.pop () ) 
			{
				x = q.front();
				for(int k=0 ; k<v[x].size() ; k++)
					if ( viz[v[x][k]] == 0 )
						{
							q.push(v[x][k]);
							viz[v[x][k]] = 1;
						}
					
			}
		}
	}
}
int main ()
{

	freopen("dfs.in","r",stdin);
	read();
	solve();
	freopen("dfs.out","w",stdout);
	printf("%d",nr);
	
	return 0;
}