POJ-3687: Labeling Balls

keyword

有向グラフ　トポロジカルソート　辞書順最小　C++

問題概要

ノード数N(<200)、辺の数M(<40000)の有向グラフが与えられる。このとき、グラフがDAGであるならば、ノードに辞書順最小のトポロジカル順序を与える問題。

解法

辞書順最小はGreedy。まず前処理として、DAGの判定も込めてWarshall-Floydしておく。ノード数の小さい順に次の処理をしていく。

• 下流にある未処理のノードの数だけ小さい番号を確保して置かなければならないので、自分には小さい方から数えて(下流にある個数+1)番目の番号を割り振る。
• 下流にある全てのノードに対して再帰的に同様の処理をする。

感想

辺を選ぶ順序を適切にすれば普通のトポロジカルソートと同じように帰りがけに番号振っていけばいいと思って大分ハマった。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <string.h>
using namespace std;

const int MAX_N = 209;
bool graph[MAX_N][MAX_N];
bool used[MAX_N];
int ans[MAX_N];
int N;
set<int> unused;

void subsolve(int v){
    used[v] = true;
    int cnt = 0;
    vector<int> Q;
    for(int i=1; i<=N; i++)if(graph[v][i] && !used[i]){
        cnt++;
        Q.push_back(i);
    }
    set<int>::iterator itr = unused.begin();
    advance(itr,cnt);
    ans[v] = *itr;
    unused.erase(itr);
    sort(Q.begin(), Q.end());
    for(int i=0; i<Q.size(); i++)if(!used[Q[i]]){
        subsolve(Q[i]);
    }
}

void solve(){
    for(int k=1; k<=N; k++)for(int i=1; i<=N; i++)for(int j=1; j<=N; j++){
        graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
    }
    for(int i=1; i<=N; i++)if(graph[i][i]){
        puts("-1");
        return ;
    }

    unused.clear();
    for(int i=1; i<=N; i++)unused.insert(i);
    memset(used,0,sizeof(used));

    for(int i=1; i<=N; i++)if(!used[i]){
        subsolve(i);
    }

    for(int i=1; i<=N; i++){
        printf("%d%c",ans[i], i==N?'\n':' ');
    }
}

int main(){
    int T;
    for(scanf("%d",&T);T--;){
        int M;
        scanf("%d%d",&N,&M);
        for(int i=1; i<=N; i++)for(int j=1; j<=N; j++)
            graph[i][j] = false;
        for(int i=0; i<M; i++){
            int a, b;
            scanf("%d%d",&a,&b);
            graph[b][a] = true;
        }
        solve();
    }
    return 0;
}