POJ 3687 Labeling Balls：拓扑序列

POJ 3687 Labeling Balls：拓扑序列2015-02-25Labeling Balls：http://poj.org/problem？id=3687

大意：n个重量分别为1-n的小球，给定一些小球间的重量关系。在符合重量关系的前提下，先输出编号小的球。

思路：也是一道很简单的拓扑排序，不过要倒着来，注意一下要判重边。

#include <string.h>#include <iostream>using namespace std;int Map[210][210], indegree[210], Ans[210];int n, m, x, y;int i, j;void Topo（）{for（i = n; i >= 1; i--）{for（j = n; j >= 1; j--）{if（indegree[j] == 0）{indegree[j]--;Ans[j] = i;for（int k = 1; k <= n; k++）{if（Map[j][k] == 1）{indegree[k]--;}}break;}}if（j < 1）{break;}}if（i >= 1）cout << "-1" << endl;else{for（i = 1; i <= n; i++）{if（i < n）{cout << Ans[i] << " ";}else{cout << Ans[i] << endl;}}}}void Solve（）{int cases;cin >> cases;while（cases--）{memset（Map, 0, sizeof（Map））;memset（indegree, 0, sizeof（indegree））;cin >> n >> m;for（i = 1; i <= m; i++）{cin >> x >> y;if（！Map[y][x]）{Map[y][x] = 1;indegree[x]++;}}Topo（）;}}int main（）{Solve（）;return 0;}