トポロジカルソート

今日は、SRMの過去問をトポロジカルソートで解いてみた。

有向グラフのトポロジーに注目したソートですが、トポロジーって一体・・・、

なんか他にも似たような言葉がたくさんあるような・・・。

ちょっとまとめてみます。

• トポロジー　　 幾何学的な相対位置、ネットワークの接続状況など
• エントロピー　物事の煩雑さ
• オントロジー　物事の概念を意味・関係などで定義したもの

で、今回はトポロジカルソートです。

簡単に言うと、どの接点も自分の子孫より先に来るようにソートすることです。

Makeでコンパイルする順序を決めたり、PERTのスケジュール管理で使われるみたいです。

ではさっそく解いてみます。

問題は、こちら。

http://www.topcoder.com/stat?c=problem_statement&pm=9824&rd=12179

ソースは、これ。

定型的なアルゴリズムがあるようですが、とりあえず、自己流で出力辺の無い接点を取り出して、その接点はグラフ集合からのぞいて・・・を繰り返しています。

bool dn[64];
class CorporationSalary {
public:
 long long totalSalary(vector<string> relations) {
     memset(dn, 0, sizeof(dn));

     VI idx;
     int sz = relations.size();
     while (accumulate(dn, dn+sz, 0) < sz) {
         REP(i, relations.size()) {
             if (dn[i]) continue;
             bool lst = true;
             REP(j, relations[i].size()) {
                 if (dn[j]) continue;
                 if (relations[i][j] == 'Y') {
                     lst = false;
                     break;
                 }
             }
             if (lst) {
                 idx.PB(i);
                 dn[i] = 1;
             }
         }
     }

     long long ret = 0LL;
     long long sl[sz];
     fill(sl, sl+sz, 0LL);

     REP(i, sz) {
         long long m = 0LL;
         REP(j, sz) {
             if (relations[idx[i]][j] == 'Y')
                 m += sl[j];
         }
         sl[idx[i]] = m ? m : 1;
         ret += sl[idx[i]];
     }
     return ret;
 }
};