Cod sursa(job #819629)

Utilizator monica11Szekely Monica monica11 Data 19 noiembrie 2012 15:10:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
#define dim 100005
using namespace std;
typedef vector<int>::iterator it;
vector<int>g[dim];
int n,m,c;
bitset <dim> viz;
void dfs(int i)
{
	for(it ii=g[i].begin();ii!=g[i].end();++ii)
	if(!viz[*ii])
	{
		viz[*ii]=1;
		dfs(*ii);
	}
}
int main ()
{
	int i,a,b;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(i=1;i<=n;++i)
	if(!viz[i])
	{
		c++;
		dfs(i);
	}
	printf("%d",c);
}