4023978_wa.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;
int tmp[300][300];

void check()
{
	int i, j;

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			tmp[i][j] = map[i][j];
		}
	}
	int td[300];
	for (i = 0; i < n; i++)
	{
		td[i] = d[i];
	}
	int pp[300], ff = 0, rr = 0;
	for (i = 0; i < n; i++)
	{
		if (!td[i])
			pp[rr++] = i;
	}
	while (ff != rr)
	{
		int v = pp[ff++];
		for (i = 0; i < n; i++)
		{
			if (map[v][i])
			{
				td[i]--;
				if (td[i] == 0)
				{
					pp[rr++] = i;
				}
			}
		}
	}
	error = (rr != n);
}

int main()
{
	int cas;
	int i, j, 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[a - 1][b - 1] = 1;
			d[b - 1]++;
		}
		error = 0;
		check();
		if (error)
		{
			puts("-1");
			continue;
		}
		int cur, sign[200];
		memset(sign, 0, sizeof(sign));
		int index = 0;
		for (i = 1; i <= n; i++)
        {
            cur = 0;
            while (d[cur] || sign[cur])
            {
				cur++;
			}
            sign[cur] = 1;
            label[index++] = cur;
            for (j = 0; j < n; j++)
            if (map[cur][j])
            {
				d[j]--;
			}
        }
		printf("%d", label[0] + 1);
		for (i = 1; i < n; i++)
		{
			printf(" %d", label[i] + 1);
		}
		puts("");
	}
	return 0;
}