HDU1285

hdu1285.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define sd(x) scanf("%d",&x)
#define sdd(x,y) scanf("%d%d",&x,&y)
#define sddd(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define slflf(x,y) scanf("%lf%lf",&x,&y)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;


//L is Empty list that will contain the sorted elements
//S is Set of all nodes with no incoming edges
//while S is non-empty do
//    remove a node n from S
//    add n to tail of L
//    for each node m with an edge e from n to m do
//        remove edge e from the graph
//        if m has no other incoming edges then
//            insert m into S
//if graph has edges then
//    return error (graph has at least one cycle)
//else
//    return L (a topologically sorted order)

class Topo
{
	const static int MAXN = 505;
	int n, m;
	int G[MAXN][MAXN], income[MAXN], L[MAXN];
public:
	Topo(int _n, int _m)
	{
		n = _n;
		m = _m;
		memset(G, 0, sizeof(G));
		memset(income, 0, sizeof(income));
		for (int i = 0; i < m; i++)
		{
			int a, b;
			sdd(a, b);
			if (!G[a][b]) income[b]++;
			G[a][b] = 1;
		}
	}

	void Sort()
	{
		int cur = 1;
		while (1)
		{
			int u = 1;
			while (income[u] != 0)
			{
				u++;
				if (u > n) break;
			}
			if (u > n) break;
			income[u] = -1;
			L[cur++] = u;
			for (int i = 1; i <= n; i++)
			{
				if (G[u][i] > 0)
				{
					income[i]--;
					G[u][i] = -1;
				}
			}
		}
		output();
	}

	void output()
	{

		for (int i = 1; i <= n; i++){
			printf("%d", L[i]);
			if (i != n) printf(" ");
		}
		printf("\n");

	}

};

int main(void)
{
	int n, m;
	Topo *a;
	while (~sdd(n, m)){
		a = new Topo(n, m);
		a->Sort();
		delete a;
	}
	return 0;
}