4024246_ac_344ms_248k.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, k;
	for(i = 1; i <= n; i ++)
		for(j = 1; j <= n; j ++)if(i != j){
			for(k = 1; k <= n; k ++)if(i != k)
				if(tmp[j][i] && tmp[i][k]) tmp[j][k] = 1;
		}

		for(i = 1; i <= n; i ++)
			if(tmp[i][i]) error = 1;
}

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));
		memset(tmp, 0, sizeof(tmp));
		while (m--)
		{
			scanf("%d%d", &a, &b);
			tmp[a][b] = 1;
			map[b - 1][a - 1] = 1;
			d[a - 1]++;
		}
		error = 0;
		check();
		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;
}


1
10 5
1 4
3 5
4 5
2 6
9 1
*/


#include<iostream>
using namespace std;
bool a[205][205];
int pos[205], n, m;
bool check()
{
	int i, j, k, t;
	for(i = 1; i <= n; i ++)
		for(j = 1; j <= n; j ++)if(i != j){
			for(k = 1; k <= n; k ++)if(i != k)
				if(a[j][i] && a[i][k]) a[j][k] = 1;
		}

		for(i = 1; i <= n; i ++)
			if(a[i][i]) return 1;

			return 0;
}
void oper()
{
	int i, j, k, t;
	for(i = 1; i <= n; i ++){
		k = pos[i];

		for(j = 1 ; j <= n; j ++){
			if(a[i][j] && pos[j] < k)
				k = pos[j];
		}
		t = pos[i];
		pos[i] = k;
		for(j = 1; j <= n; j ++){
			if(i != j && pos[j] >= k && pos[j] < t)
				pos[j] ++;
		}
	}
}
int main()
{
	int i, j, k, t, tcase;
	scanf("%d", & tcase);
	while(tcase --)
	{
		scanf("%d %d", & n, & m);

		memset(a, 0, sizeof(a));
		for(i = 1; i <= n; i ++)
			pos[i] = i;

		for(i = 0; i < m; i ++){
			scanf("%d %d", & k, & t);
			a[k][t] = 1;
		}
		if(check() == 1) {
			printf("-1\n");
			continue;
		}
		oper();
		for(i = 1; i < n; i ++)
			printf("%d ", pos[i]);
		printf("%d\n", pos[i]);
	}
	return 0;
}