Cod sursa(job #631548)

Utilizator tomaAndrei Toma toma Data 8 noiembrie 2011 16:07:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<stdio.h>
#include<vector>
#define pb push_back
#define Nmax 100001

using namespace std;

int nr,N,M,i,x,y;
vector<int> a[Nmax];
vector<bool> ok(Nmax,false);

void DF(int nod)
{
	ok[nod]=true;
	for (vector<int>::iterator it=a[nod].begin();it!=a[nod].end();it++)
		if (!ok[*it]) DF(*it);
}

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",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
	for (i=1;i<=N;i++)
		if (!ok[i])
		{
			DF(i);
			nr++;
		}
	printf("%d\n",nr);
}