预测名次

猫猫比赛-预测名次

问题描述

一共有 N 只猫猫，编号依次为1, 2, 3, …, N 进行比赛，求字典序最小的名次序列。

Input

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

Output

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

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample

Input: 
4 3
1 2
2 3
4 3

Output: 
1 2 4 3

Limitation

Time limit		1000 ms
Memory limit	32768 kB

解题思路

比赛问题，若A胜B，A胜C，B胜C，则A的名次在B、C的前面，B的名次在C的前面，可以构成有向无环图，因此可以使用拓扑排序。

集合U为点集，每次选出入度为零的点s，加入结果集合S中，并从U中删除s，并修改s指向的点的入度，以此循环，直至U为空。

由于每次选的入度为零的点有多个，本题要求以字典序输出，因此可用优先级队列储存每次选取的入度为零的点，然后进行BFS，遍历全图。

源代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct node {
	int ele;
	node* next;
	node() { ele = -1; next = NULL; }
	node(int e) :ele(e) { next = NULL; }
};

class linkedList {
private:
	node* header;
	int size;
public:
	linkedList() { header = NULL; size = 0; }
	~linkedList() { clear(); }
	int getSize() { return size; }
	node* getHeader() { return header; }
	void add(int ele) {
		node* p = new node(ele);
		if (header == NULL)
			header = p;
		else {
			node* temp = header;
			node* temp2 = NULL;
			while (temp != NULL) {
				temp2 = temp;
				temp = temp->next;
			}
			temp2->next = p;
		}
		size++;
	}
	void clear() {
		node* temp = header;
		node* ttemp = NULL;
		while (temp != NULL) {
			ttemp = temp;
			temp = temp->next;
			ttemp = NULL;
		}
		header = NULL;
		delete temp;
		delete ttemp;
		delete header;
		size = 0;
	}
};

const int maxN = 510;

class graph {
private:
	linkedList arr[maxN];
	int inDeg[maxN];
	int size;
public:
	graph() { size = 0; }
	graph(int n) { size = n; setIN(); }
	~graph() {  }
	void setIN() {
		for (int i = 0; i <= size; i++)
			inDeg[i] = 0;
	}
	void add(int p1, int p2) {
		arr[p1].add(p2);
		inDeg[p2]++;
	}
	vector<int> topoSort() {
		priority_queue<int, vector<int>, greater<int>> q;
		vector<int> ans;
		for (int i = 1; i <= size; i++)
			if (inDeg[i] == 0)
				q.push(i);//所有入度为零的点入队
		while (!q.empty()) {
			int x = q.top();//选出队首元素 开始遍历
			q.pop();
			ans.push_back(x);
			for (node* p = arr[x].getHeader(); p != NULL; p = p->next) {
				int ele = p->ele;
				inDeg[ele]--;//与之相邻的点入度 -1
				if (inDeg[ele] == 0)//入度为零 可入队
					q.push(ele);
			}
		}
		return ans;
	}
};

int main() {
	int n, m;
	while (!(cin >> n >> m).eof()) {
		graph G(n);
		for (int i = 0; i < m; i++) {
			int p1, p2;
			cin >> p1 >> p2;
			G.add(p1, p2);
		}
		vector<int> v = G.topoSort();
		for (int i = 0; i < v.size() - 1; i++)
			cout << v[i] << " ";
		cout << v[v.size() - 1] << endl;
	}

	return 0;
}