Cod sursa(job #294086)

Utilizator whiskeyOzzy Osbourne whiskey Data 2 aprilie 2009 12:18:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <vector>
#include <list>
#include <queue>
#define pb push_back
using namespace std;

int n, m;
vector< list<int> > vecini;
vector<bool> sel;
queue<int> c;

void read();
void solve();

int main()
{
	read();
	solve();
	return 0;
}

void solve()
{
	FILE *fout = fopen("sortaret.out", "w");
	int nod;
	list<int>::iterator i, sfarsit;
	while (!c.empty())
	{
		nod = c.front();
		sfarsit = vecini[nod].end();
		for (i = vecini[nod].begin(); i != sfarsit; ++i)
		{
			if (sel[*i])
			{
				c.push(*i);
				sel[*i] = 0;
			}
		}
		fprintf(fout, "%d ", nod);
		c.pop();
	}
	fprintf(fout, "\n");
	fclose(fout);
}

void read()
{
	int i, x, y;
	FILE *fin = fopen("sortaret.in", "r");
	fscanf(fin, "%d%d", &n, &m);
	vecini.resize(n + 1);
	sel.resize(n + 1, 0);
	for (i = 1; i <= m; ++i)
	{
		fscanf(fin, "%d%d", &x, &y);
		vecini[x].pb(y);
		sel[y] = 1;
	}
	fclose(fin);
	for (i = 1; i <= n; ++i)
	{
		if (!sel[i])
		{
			c.push(i);
		}
	}
}