Cod sursa(job #926460)

Utilizator BeniaminMarcu Beniamin Beniamin Data 25 martie 2013 11:06:55
Problema Parcurgere DFS - componente conexe Scor 5
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);
	}
}

void df(int nod)
{
    nr++;
	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)
			df(i);
}

void afisare()
{
    freopen("dfs.out", "w",stdout);
	printf("%lu" , nr);

}

int main()
{
	citire();
	componente_conexe();
	afisare();

	return 0;
}