B-猫猫向前冲（拓扑排序

题意：

input:

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示猫猫的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即编号为 P1 的猫猫赢了编号为 P2 的猫猫。

output:

给出一个符合要求的字典序最小的排名。输出时猫猫的编号之间有空格，最后一名后面没有空格!

样例：
输入：

4 3
1 2
2 3
4 3

输出：

1 2 4 3

思路：

分析题意，可知需要用拓扑排序来解题。即对输出的每对猫，A,B，化作一条A到B的路线。通过一个数组rd[] 记录下每个点的入度，在构建图的时候记录下，每个点的入度。在图构建完成的时候，可以遍历找出入度为0的点，因为需要字典序最小的排序，故将这些点放入优先队列。每次从队首取出一个点的时候，将其放到队列中。并以这个点开始，遍历其所能到达的所有点，并将其能到达的所有的点的rd[]值减去1，减去的同时，判断若入度已经为0，则将这些点也加入到优先队列中去。最后等优先队列为空的时候，则图，遍历完成。输出队列中的点即可。

代码：

#include <cstdio>
#include <algorithm> 
#include <iostream>
#include <string.h> 
#include <queue>
#include <cmath>
using namespace std;

queue<int> q1;
priority_queue<int> q2;

int N, M, p1, p2;
struct Edge {
	int to, next;
}e[1000];
int tot;
int head[505];
int rd[505];

// to到那个点   从那个点 
void add_edge(int t, int f) {
	rd[t]++;     //入度增加 
	e[tot].to = t;
	e[tot].next = head[f];
	head[f] = tot;
	tot++;
}

void bfs() {
	while (q2.size()) {
		int x = -q2.top(); q2.pop();
		q1.push(x);
		int y = head[x];
		while (y != -1) {  //y->to
			int r1 = e[y].to;
			rd[r1]--;
			if (rd[r1] == 0) q2.push(-r1);
			y = e[y].next;
		}
	}
}


int main() {
	ios::sync_with_stdio(0);
	while (cin >> N >> M) {
		tot = 0;
		for (int i = 1; i <= N; i++) {
			head[i] = -1;
			rd[i] = 0;
		}
		for (int i = 0; i < M; i++) {
			cin >> p1 >> p2;
			add_edge(p2, p1);
		}
		for (int i = 1; i <= N; i++) {
			if (rd[i] == 0) q2.push(-i);
		}
		bfs();
		int x = q1.front(); q1.pop();
		cout << x;
		while (q1.size()) {
			x = q1.front(); q1.pop();
			cout << " " << x;
		}
		cout << endl;
	}
	return 0;
}