Cod sursa(job #858274)

Utilizator aladinaladin aladinn aladin Data 18 ianuarie 2013 19:06:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;

vector <int> v[100009];
int ok[100009];

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

int main()
{
	int n,m,i,x,y,sol=0;
	
	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);
		v[x].pb(y);
		v[y].pb(x);
	}
	for (i=1;i<=n;++i)
		if (!ok[i])
			df(i),++sol;
	printf("%d\n",sol);
return 0;
}