Cod sursa(job #926448)

Utilizator BeniaminMarcu Beniamin Beniamin Data 25 martie 2013 11:03:58
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;

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

vector <int> vecin[MAX];
vector <int> lista;

int v_culoare[MAX];
int n , m;

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

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;
    lista.push_back(nod);
}

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

void afisare_lista()
{
	vector <int> :: iterator it;
	freopen("sortaret.out", "w" , stdout);
    /*for(it = lista.end(); it != lista.begin(); --it)
	{
		printf("%d " , *it);
	}*/
	it = lista.end();
	do{
        --it;
        printf("%d " , *it);
	}while(it != lista.begin());
}

int main()
{
	citire();
	sort_t();
	afisare_lista();

	return 0;
}