Cod sursa(job #152974)

Utilizator za_wolfpalianos cristian za_wolf Data 9 martie 2008 22:51:59
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<stdio.h>
#include<vector>
using namespace std;
#define NMAX 100010
#define pb push_back

int y[NMAX],z[NMAX],i,n,m,a,b,s;
vector <int> x[NMAX];

void df(int k)
{
	z[k]=1;
	for (int i=1;i<=y[k];i++)
		if (!z[x[k][i]])
			df(x[k][i]);
}
int main()
{
	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);
		y[a]++;
		x[a].pb(b);
		y[b]++;
		x[b].pb(a);
	}

	for (i=1;i<=n;i++)
		if (!z[i])
		{
			s++;
			df(i);
		}
	printf("%d\n",s);

	return 0;
}