Cod sursa(job #350258)

Utilizator bogdanacmDrutu Bogdan bogdanacm Data 23 septembrie 2009 09:53:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define pb push_back
#define NMAX 100005

vector <int> G[NMAX];
int viz[NMAX],N,M;

void dfs(int k)
{
	int i;
	viz[k]=1;
	for ( i = 0 ; i < G[k].size() ; i++)
		if (!viz[G[k][i]])
			dfs(G[k][i]);
}

int main()
{
	int i,j,k=0,x,y;
	freopen("dfs.in", "rt", stdin);
	freopen("dfs.out", "wt", stdout);

	scanf("%d %d",&N,&M);

	for (i=0;i<M;i++)
	{
		scanf("%d %d",&x,&y);
		G[x].pb(y);
		G[y].pb(x);
	}

	for ( i=1 ; i <= N ; i++)
		if (!viz[i])
			dfs(i),k++;

	printf("%d\n",k);
	return 0;
}