Cod sursa(job #548788)

Utilizator IAmASuperCerealVictor Andrei IAmASuperCereal Data 7 martie 2011 20:02:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
#include <vector>

#define NMAX 100001
#define input "dfs.in"
#define output "dfs.out"

using namespace std;

vector<int> G[NMAX];
int x,y,n,m,nr;
bool v[NMAX];

void DFS(int nod)
{
	v[nod]=true;
	for (int i=0;i<G[nod].size();i++) 
	{
			int y = G[nod][i];
			if (!v[y]) 
				DFS(y);
	}
}

void open()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);
}

void read()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void count()
{
	for (int i=1;i<=n;i++) 
		if (!v[i]) 
		{
			nr++; 
			DFS(i);
		}
	printf("%d\n",nr);
}

int main()
{
	open();
	read();
	count();
	return 0;
}