Cod sursa(job #926999)

Utilizator BeniaminMarcu Beniamin Beniamin Data 25 martie 2013 15:21:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;

#define alb 0
#define gri 1
#define negru 2
#define MAX 100001

vector <int> vecin[MAX];

long v_culoare[MAX];
long unsigned n , m, nr = 0;

void citire()
{
	long unsigned i, x, y;
	freopen( "dfs.in", "r", stdin);
    scanf("%lu%lu ", &n , &m);
    for(i = m; i > 0; i--)
	{
       scanf("%lu%lu", &x ,&y);
	   vecin[x].push_back(y);
	   vecin[y].push_back(x);
	}
}

void df(int nod)
{
	v_culoare[nod] = gri;
	vector<int>::iterator it;
	for(it = vecin[nod].begin(); it != vecin[nod].end(); ++it)
        if(v_culoare[*it] == alb )
			df(*it);
	v_culoare[nod] = negru;
}

void componente_conexe()
{
	int i;
	for(i = n; i > 0; i--)
		if(v_culoare[i] == alb)
		{
		     nr++;
		    df(i);
		}
}

int main()
{
	citire();
	componente_conexe();
	freopen("dfs.out", "w", stdout);
	printf("%lu", nr);

	return 0;
}