読者です 読者をやめる 読者になる 読者になる

yukicoder ★★★ No.416 旅行会社

yukicoder 競プロ

問題

No.416 旅行会社 - yukicoder

考察

1の島から各島にたどり着けるかどうかはUnionFind木を作ればわかります。
が、削ることはできないため、橋を削る都度作っているとTLEしてしまいます。
かと言って、橋が落とされた時の変化を求めるのも大変そうです。

いろいろと考えてみると、橋を作ってそれが1の島に繋がるかどうか、というのはUnionFindですんなり行けそうな感じを受けます。
ということはクエリを逆から処理すればいい!という閃きがやってくるかと思います。

具体的な手順に落としこむと、以下のような処理になります。

  1. 壊れた橋以外でグラフとUnionFindを作る
  2. 答え用の配列を-1で初期化
  3. クエリを逆順からループ
    1. 片方の島が1に繋がっており、もう片方が繋がっていないなら、繋がっていない方のグループの答え配列を更新
    2. グラフ、UnionFindに橋を加える
  4. 最後まで辿りつけない島は0を、それ以外は答え配列の中身を出力

「繋がっていない方のグループ」を辿る処理で悩みましたが、↑の処理に含まれているように、グラフを更新しdfsをしました。
また、「与えられた橋から削る」のがなんとなく(計算量的に)大変そうだったので、一時的にmapに持たせるという変なことをしています。

コード

class UnionFind {
private:
    vi par;
    vi rank;

    int find(int x) {
        if(par[x] == x)
            return x;
        else
            return par[x] = find(par[x]);
    }

public:
    UnionFind(int n) {
        rep(i,n) {
            par.push_back(i);
            rank.push_back(0);
        }
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x==y) return;

        if(rank[x] < rank[y])
            par[x] = y;
        else {
            par[y] = x;
            if(rank[x] == rank[y])
                rank[x]++;
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return rank[find(x)];
    }
};

const int MAX_N = (int)(1e5) + 10;
vi edges[MAX_N];
bool used[MAX_N];
int ans[MAX_N];

void dfs(int x, int v) {
    used[x] = true;
    ans[x] = v;

    tr(it, edges[x]) {
        if(!used[*it]) {
            dfs(*it, v);
        }
    }
}

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;

    map<pii, bool> has_edge;
    rep(i, M) {
        int A, B;
        cin >> A >> B;
        --A, --B;
        has_edge[mp(A,B)] = true;
        has_edge[mp(B,A)] = true;
    }

    vector<pii> queries(Q);
    rep(i, Q) {
        int C, D;
        cin >> C >> D;
        --C, --D;
        queries[i] = mp(C, D);
        has_edge[mp(C,D)] = false;
        has_edge[mp(D,C)] = false;
    }

    UnionFind uf(N);
    tr(it, has_edge) {
        if(it->second) {
            int x = it->first.first;
            int y = it->first.second;
            uf.unite(x, y);
            edges[x].push_back(y);
            edges[y].push_back(x);
        }
    }

    memset(ans, -1, sizeof(ans));
    for(int i=Q-1; i>=0; i--) {
        int x = queries[i].first;
        int y = queries[i].second;
        if(!uf.same(0, x) && uf.same(0, y)) {
            dfs(x, i+1);
        }
        if(uf.same(0,x) && !uf.same(0, y)) {
            dfs(y, i+1);
        }

        uf.unite(x, y);
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    REP(i, 1, N) {
        if(!uf.same(0, i))
            cout << 0 << endl;
        else
            cout << ans[i] << endl;
    }

    return 0;
}

備考

解説を見ると、「データ構造をマージする一般的なテク」なるものがあるとのこと。
一般的なのに全然知りませんでしたorz
これを使うと、↑のdfsみたいな面倒なことはしなくても間に合いそうです。
若干のショック。

topcoder.g.hatena.ne.jp