SRM 299 DIV2 1000 StrangeParticles

問題概要

　空間を飛び回る粒子があります。２つの粒子がぶつかると、以下の３つのうちどれかが起きます。

1. 最初の粒子が消滅する
2. ２つ目の粒子が消滅する
3. 何も起こらない

粒子の数は50個以下です。任意のペアの粒子が衝突した場合、上の1-3のうちどれが起こるかという情報が与えられます。その情報を元にランダムな回数・順番で粒子同士が衝突したとき、最終的に残る粒子の数の最小値を求めよ。

方針

　強連結成分（SCC）分解して、DAGにして、DAGの根の数が答え。強連結成分分解は、DFSを二回やる方法が有名ですが、この問題では節点数が小さいのでワーシャルフロイド法を利用したやり方でもできます。

1. 粒子Aが粒子Bを消すことができるとき、AからBへ有向枝をはる。
2. ワーシャルフロイドで、1.の推移閉包を求める。
3. i->jパス、j->iパスが同時に存在するとき、閉路と考える。これを利用して、SCCにグルーピングしていく。
4. SCCを1つの節点とみなして、枝をはり直してDAGにする。
5. 各接点の入次数を数える。

まあソース見た方が早いです。DFS2回バージョンは直感的に理解するのが難しいですが、こっちのワーシャルフロイドバージョンは直感的につかみやすいですねー。実装量も少ないので、計算量に余裕がある場合はこっちのほうがいいかもしれません。

ソースコード

bool win[50][50];
int id[50];
int d[50];

class StrangeParticles {
public:
    int remain(vector<string> interacts) {
        int N = interacts.size();

        memset(win, 0, sizeof(win));
        REP(i, N) REP(j, N) if (i == j || interacts[i][j] == '-') win[i][j] = 1;
        REP(k, N) REP(i, N) REP(j, N) win[i][j] |= win[i][k] & win[k][j];

        memset(id, -1, sizeof(id));
        int p = 0;
        REP(i, N) {
            if (id[i] == -1) {
                FOR (j, i, N) if (win[i][j] & win[j][i]) id[j] = p;
                ++p;
            }
        }

        memset(d, 0, sizeof(d));
        REP(i, N) REP(j, N) if (win[i][j]) {
            if (id[i] != id[j])
                d[id[j]]++;
        }

        int ret = 0;
        REP(i, p) if (d[i] == 0) ++ret;

        return ret;
    }
};