SGU 230. Weighings (拓扑排序)

浏览数：43 / 时间：2015年06月08日

题意：

      给出质量为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

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢