Cod sursa(job #589925)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 14 mai 2011 15:27:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
/*
	bfs, dar in loc sa pun in coada vecinii nodului curent (si sa-i
marchez ca vizitati), retin un contor cu cati tati mai am de adaugat
ai fiecarui nod si in bfs micsorez contorul. pun in coada doar cand
contorul ii ajunge la 0.
*/

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int N = 50005;

int n;
vector<int> fiu[N];
int contor_pred[N]={0};
bool are_tata[N];
queue<int> coada;
int sol[N],nsol=0;//nodurile in ordinea parcursa;

void citire()
{
	int a,b,m;
	scanf("%d %d",&n,&m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d %d",&a,&b);
		fiu[a].push_back(b);
		++contor_pred[b];
		are_tata[b] = true;
	}
}

void bfs_cu_contoruri()
{
	int nod,dest;
	//golire coada, nu este necesara
	for (int i = 1; i <= n; ++i)//pun in coada nodurile fara tati
		if (!are_tata[i])
			coada.push(i);
	while (!coada.empty())
	{
		nod = coada.front();
		sol[++nsol] = nod;
		for (unsigned int i = 0; i < fiu[nod].size(); ++i)
		{
			dest = fiu[nod][i];
			--contor_pred[dest];
			if (contor_pred[dest] == 0)
				coada.push(dest);
		}
		coada.pop();
	}
}

void scriere()
{
	for (int i = 1; i <= n; ++i)
		printf("%d ",sol[i]);
}

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	citire();
	bfs_cu_contoruri();
	scriere();
	return 0;
}