4024090_wa.cpp

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

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

using namespace std;

int n, m;
int index[300];
int cnt, top;
int map[300][300];
int error;
int visited[300];
int d[300];
int heap[300], p;
int root;
int tmp[300][300];
int td[300];
void check()
{
	int i, j;

	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			tmp[i][j] = map[i][j];
		}
	}
	
	int pp[300], ff = 0, rr = 0;
	for (i = 1; i <= n; i++)
	{
		if (!td[i])
			pp[rr++] = i;
	}
	while (ff != rr)
	{
		int v = pp[ff++];
		for (i = 1; 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);
		memset(d, 0, sizeof(d));
		memset(map, 0, sizeof(map));
		
		while (m--)
		{
			scanf("%d%d", &a, &b);
			map[b][a] = 1;
			d[b]++;
			td[a]++;
		}
		error = 0;
		check();
		if (error)
		{
			puts("-1");
			continue;
		}
		int cur, sign[300];
		memset(sign, 0, sizeof(sign));
		cnt = 1;
		top = 0;
		for(i=1;i<=n;i++)
        {
            cur=1;
            while(d[cur]||sign[cur])
            cur++;
            sign[cur]=1;
            index[top++]=cur;
            for(j=1;j<=n;j++)
            if(map[j][cur])
            d[j]--;
        }

		printf("%d", index[0]);
		for (i = 1; i < n; i++)
		{
			printf(" %d", index[i]);
		}
		puts("");
	}
	return 0;
}