学步园

题目连接

直接排序

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int N, M;
const int MAXN = 501, MAXM = MAXN*MAXN/2;
int g[MAXN][MAXN], in[MAXN],  ans[MAXN];
int topoSort()
{
	int in1[MAXN];
	for(int i = 0; i < N; i++) in1[i] = in[i];
	for(int k = 0; k < N; k++)
	{
		int i = 0;
		while(in1[i]!=0)
		{
			i++;
			if(i >= N)
				return 2;	//成环，矛盾
		}
		ans[k] = i;
		in1[i]--;
		for(int j = 0; j < N; j++)
			if(g[i][j])
				in1[j]--;
	}
	for(int i = 0; i < N-1; i++)
	{
		int ok = 0;
		//for(int j = 0; j < N; j++)
			if(g[ans[i]][ans[i+1]])
				ok = 1;
		if(!ok)
			return 1;	//不能确定排列序列
	}
	return 0;			//确定排序
}
int main()
{
	//freopen("in.txt", "r", stdin);
	while(scanf("%d%d", &N, &M)!=EOF && !(!N&&!M))
	{
		memset(g, 0, sizeof(g));
		memset(in, 0, sizeof(in));
		for(int i = 0; i < M; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			g[u-1][v-1] = 1;
			in[v-1]++;
		}
		topoSort();
		for(int i = 0; i < N; i++)
			printf(i!=N-1 ? "%d " : "%d\n", ans[i]+1);
	}
	return 0;
}