Cod sursa(job #500524)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 12 noiembrie 2010 15:07:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <vector>
#include <string.h>
#define pb push_back

using namespace std;

vector<int> a[100001];
int i,n,m,con,x,y;
bool used[100001];

void df(int ind)
{
	vector<int>::iterator it;

	used[ind]=true;
	for (it=a[ind].begin();it!=a[ind].end();it++)
	{
		if (!used[*it])
			df(*it);
	}
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for (i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
	
	con=0;
	memset(used,false,sizeof(used));
	
	i=1;
	while (i<=n)
	{
		if (!used[i])
		{
			con++;
			df(i);
		}
		i++;
	}
	
	printf("%d\n",con);
	
	return 0;
}