Uva 10305 奇妙的拓扑

一、题意

给定一个n和一个m。
n表示有n个数1...n；m表示有m对大小关系。
接下来打印出m对(i, j) 表示 i < j；
要求输出一个这n个数可能的从小到大的排列。

二、解析

显然是拓扑排序。
拓扑排序可以通过dfs的方法，也可以通过队列的方法。我比较喜欢用队列，只需要维护一个Next数组存放每个点所指向的点集（就叫出度点好了），以及一个inNum数组记录每个点当前的入度大小。当一个点的入度为0时就可以放心的把该点放入队列，然后更新它的出度点的入度值。

三、代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 100 + 5;
vector<int> Next[maxn], ans;
int inNum[maxn];

int main() {
    int n, m;
    while(cin >> n >> m && n) {
        for(int i = 0; i < n; i ++) Next[i].clear(), inNum[i] = 0;
        ans.clear();
        while(m --) {
            int x, y;
            cin >> x >> y;
            Next[x].push_back(y);
            inNum[y] ++;
        }
        queue<int> ready;
        for(int i = 1; i <= n; i ++) if(inNum[i] == 0) ready.push(i);
        while(!ready.empty()) {
            int u = ready.front();
            ready.pop();
            ans.push_back(u);
            for(int v : Next[u]) if(inNum[v] > 0){
                inNum[v] --;
                if(inNum[v] == 0) ready.push(v);
            }
        }
        for(int i = 0; i < ans.size(); i ++) {
            if(i) cout << " ";
            cout << ans[i];
        }
        cout << endl;
    }
}

四、归纳

• 拓扑排序的基本写法，要牢记。