SGU 230. Weighings (拓扑排序)

时间：2015-05-17 21:27:10 收藏：0 阅读：238

题意：

给出质量为1~n的n个箱子的m对轻重关系，输出一种可能的箱子的质量排列。

Solution:

拓扑排序，注意要处理重边。

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

const int N = 209;

queue<int> q;
bool G[N][N];
int deg[N], ans[N];
int n, m;

int main()
{
    ios::sync_with_stdio (0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        if(!G[u][v]){
            G[u][v]=1;
            deg[v]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (deg[i]==0) q.push (i);
    }
    int now = 0;
    while (!q.empty() ) {
        int u = q.front(); q.pop();
        ans[u] = ++now;
        for (int i = 1; i <= n; i++) {
            if (G[u][i] && (--deg[i]) == 0) {
                q.push (i);
            }
        }
    }
    if (now == n) {
        for (int i = 1; i <= n; i++)
            cout << ans[i] << ‘ ‘;
    }
    else {
        cout << "No solution\n";
    }
    return 0;
}

View Code

原文：http://www.cnblogs.com/keam37/p/4510317.html