4022594_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <functional>
#include <algorithm>
#pragma comment(linker, "/STACK:16777216")

using namespace std;

int n, m;
int label[300];
int cnt;
int map[300][300];
int error;
int visited[300];
int d[300];
int heap[300], p;
int root;

void dfs(int u)
{
	int i;

	visited[u] = 1;
	for (i = 0; !error && i < n; i++)
	{
		if (map[u][i] == 1)
		{
			if (visited[i] == 1 && root == i)
			{
				error = 1;
				return ;
			}
			dfs(i);
		}
	}
}

int main()
{
	int cas;
	int i, a, b;

	scanf("%d", &cas);
	while (cas--)
	{
		scanf("%d%d", &n, &m);
		cnt = n;
		memset(d, 0, sizeof(d));
		memset(map, 0, sizeof(map));
		
		while (m--)
		{
			scanf("%d%d", &a, &b);
			map[b - 1][a - 1] = 1;
			d[a - 1]++;
		}
		error = 0;
		for (i = 0; !error && i < n; i++)
		{
			memset(visited, 0, sizeof(visited));
			root = i;
			dfs(i);
		}
		if (error)
		{
			puts("-1");
			continue;
		}
		p = 0;
		for (i = 0; i < n; i++)
		{
			if (d[i] == 0)
			{
				heap[p++] = i;
				push_heap(heap, heap + p, less <int> ());
			}
		}
		while (p)
		{
			int v = heap[0];
			pop_heap(heap, heap + p, less <int>());
			p--;
			label[v] = cnt--;
			for (i = 0; i < n; i++)
			{
				if (map[v][i])
				{
					map[v][i] = 0;
					d[i]--;
					if (d[i] == 0)
					{
						heap[p++] = i;
						push_heap(heap, heap + p, less <int>());
					}
				}
			}
			if (p >= 300) while(1);
		}
		printf("%d", label[0]);
		for (i = 1; i < n; i++)
		{
			printf(" %d", label[i]);
		}
		puts("");
	}
	return 0;
}