HDU 1285は試合の順位を確定します。

2365 ワード

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=1285
Problem Description
Nチームがあります。（1<=N<=500）、番号は1、2、3、。。。。Nは試合を行います。試合が終わったら、レフェリー委員会はすべての試合チームを出発後から順に順位を付けます。しかし、今はレフェリー委員会は直接に各チームの試合成績を獲得することができません。各試合の結果、つまりP 1がP 2に勝つことを知っています。P 2で順位を表します。P 1はP 2の前にあります。今プログラムを作って順位を決めてください。

Input
入力はいくつかのグループがあります。各グループの第一の行為は二つの数N（1<=N<=500）、M；ここで、Nはチームの個数を表し、Mは続いてM行の入力データを示す。次のM行のデータでは、各ラインにも2つの整数P 1があり、P 2はP 1チームがP 2チームに勝ったと表しています。

Output
要求に合ったランキングを提供します。出力時は列番号の間にスペースがありますが、最後の方にスペースがありません。
その他の説明：条件に該当する順位は唯一ではないかもしれません。この時、出力を要求する時、番号が小さいチームが前にあります。入力データは正しいと保証されています。つまり、入力データは必ず該当順位があります。

Sample Input

Sample Output

分析:
簡単なトポロジ順序、唯一の出現可能な場所は、同じトポロジ順序を要求する二つの番号の小さいものが前にあるということです。これは優先列または積み上げによって実現できます。
コード:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define MAXN 505
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int n, m, u, v;
bool first;
int graph[MAXN][MAXN], degree[MAXN];  //      ，       ；
priority_queue <int, vector<int>, greater<int> > q;   //    ；

void Init()
{
    RST(graph), RST(degree);    //     ；
    while(!q.empty()) q.pop();   //    ；
    for(int i=0; i<m; i++) {
        scanf("%d %d", &u, &v);
        if(!graph[u][v]) {    //    ；
            graph[u][v] = 1;
            degree[v]++;
        }
    }
    first = 1;
    for(int i=1; i<=n; i++) if(!degree[i]) q.push(i);
}

int main()
{
    while(~scanf("%d %d", &n, &m)) {
        Init();
        while(!q.empty()) {
            int current = q.top();
            q.pop();
            if(first) { printf("%d", current); first = 0; }
            else printf(" %d", current);
            for(int i=1; i<=n; i++) if(graph[current][i]) {
                degree[i]--;
                if(degree[i] == 0) q.push(i);
            }
        }
        puts("");
    }
    return 0;
}

Javaは、Arayの長さを知らずに、String Arayを動的に構成しています。

シャットダウンプログラムコード