Cod sursa(job #838284)

Utilizator Aida_SilviaStrimbeanu Aida Silvia Aida_Silvia Data 19 decembrie 2012 11:35:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<cstdio>
#include<vector>

using namespace std;

const int NMAX=100073;

vector <int> v[NMAX];
int N,M,Y,X,viz[NMAX];

void DF(int nod)
{
	unsigned int i;
	viz[nod]=1;
	for (i=0;i<v[nod].size();i++)
		if (!viz[v[nod][i]])
			DF(v[nod][i]);
		
}


int main()
{
	int conexe=0,i;
	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].push_back(Y);
			v[Y].push_back(X);
		}
	
   for( i=1;i<=N;i++)
		if (!viz[i])
			{
				DF(i);
				conexe++;
			}
		
		
	printf("%d",conexe);
	
	return 0;


}