今天刚学的拓扑排序，大概搞懂后发现这题是赤裸裸的水题。

于是按自己想法敲了一遍，用queue做的，也就是Kahn算法，复杂度o(V+E)，调完交上去，WA了。。。

于是检查了一遍又交了一发，还是WA。。。

我还以为是用queue的问题，改成stack也WA，然后干脆放弃STL，手敲了队列，还是WA了。。。

我抓狂了。

感觉没什么问题的，卡了我一个多小时。最后用样例0 1测试，发现是在输入的循环判断时出错了，他要求两个都为0时结束，我只要有一个为0就结束了。。。

坑爹，血的教训。。。

然后我把之前的代码修改后都过了，还尝试了dfs。

于是：

用queue过的：

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int maxn = 101;

int n, m;

int indegree[maxn] = {0}, gragh[maxn][maxn], res[maxn];

void topologic(void) {

	queue <int> q;

	int cnt = 0;

	for (int i = 0; i < n; i++)

		if (indegree[i] == 0)

			q.push(i);

	while (!q.empty()) {

		int tmp = q.front();

		q.pop();

		res[cnt++] = tmp;

		for (int i = 0; i < n; i++)

			if (gragh[tmp][i] != 0)

				if (--indegree[i] == 0)

					q.push(i);

	}//while

	printf("%d", res[0] + 1);

	for (int i = 1; i < cnt; i++)

		printf(" %d", res[i] + 1);

	printf("\n");

}

int main() {

	while (scanf("%d%d", &n, &m) && (n || m)) {

		memset(gragh, 0, sizeof(gragh));

		memset(indegree, 0, sizeof(indegree));

		int a, b;

		for (int i = 0; i < m; i++) {

			scanf("%d%d", &a, &b);

			gragh[a-1][b-1] = 1;

			indegree[b-1]++;

		}//for input

		/*

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < n; j++)

			printf("%d ", gragh[i][j]);

		printf("\n");

	}

	for (int i = 0; i < n; i++)

		printf("%d ", indegree[i]);

	printf("\n");

*/

		topologic();

	}//while

	return 0;

}

手敲队列：

#include <cstdio>

#include <cstring>

const int maxn = 101;

int g[maxn][maxn], id[maxn], q[maxn];

int main() {

//	freopen("in", "r", stdin);

	int n, m, a, b, tmp;

	int front, tail;

	while (scanf("%d%d", &n, &m)) {

		if (n == 0 && m == 0)

			break;

		memset(g, 0, sizeof(g));

		memset(id, 0, sizeof(id));

		front = tail = 0;

		for (int i = 0; i < m; i++)  {

			scanf("%d%d", &a, &b);

			g[a][b] = 1;

			id[b]++;

		}

		for (int i = 1; i <= n; i++)

			if (id[i] == 0)

				q[tail++] = i;

		while (tail != front) {

			tmp = q[front++];

			if (front == 1)

				printf("%d", tmp);

			else

				printf(" %d", tmp);

			for (int i = 1; i <= n; i++)

				if (g[tmp][i] != 0)

					if (--id[i] == 0)

						q[tail++] = i;

		}//while

		printf("\n");

	}//while

	return 0;

}

dfs方法：

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int maxn = 101;

int n, m, t;

int gragh[maxn][maxn], res[maxn], c[maxn];

bool dfs(int u) {

	c[u] = -1;

	for (int v = 0; v < n; v++)

		if (gragh[u][v])

			if (c[v] < 0)

				return false;

			else if (!c[v] && !dfs(v))

				return false;

	c[u] = 1;

	res[--t] = u;

	return true;

}

bool toposort() {

	t = n;

	memset(c, 0, sizeof(c));

	for (int u = 0; u < n; u++)

		if (!c[u])

			if (!dfs(u))

				return false;

	return true;

}

int main() {

	while (scanf("%d%d", &n, &m) && (n || m)) {

		memset(gragh, 0, sizeof(gragh));

		int a, b;

		for (int i = 0; i < m; i++) {

			scanf("%d%d", &a, &b);

			gragh[a-1][b-1] = 1;

		}//for input

		toposort();

		for (int i = 0; i < n; i++)

			printf("%d ", res[i] + 1);

		printf("\n");

	}//while

	return 0;

}

这次是血淋淋的教训啊：

一、输入部分一定要提前测试

二、测试数据要多一点，多想些特殊测试点

三、必须提高敲题效率。