<-- home

AtCoder ABC097 D

April 28, 2020

https://atcoder.jp/contests/abc097/tasks/arc097_b

  • 交換可能な数の間に辺をはったグラフを考える
  • 数が行き来可能なインデックスは強連結成分に含まれる
  • ある強連結成分をGとして、それに含まれる辺の総数をEとすると、少なくとも本の辺をもつ
  • 本の辺をもつとき、Gは木になる

このとき、Gに含まれる数を並べ替えて、にできるかどうかを考察する。強連結成分から適当な辺を除いて木にしたとき、実際にならべかえる方法を構築して証明する

  1. 適当な頂点を定める
  2. 葉にとなるように数を移動する
  3. Gにとなるノードがないは適当に葉を埋めるために使う
  4. 埋めた葉は、その後の数に移動に関わらないので、木から除く
  5. 以下2-4を繰り返し

実装

template<typename T>
struct UnionFind {
    i64 sz;

    vector<T> parent;
    vector<i64> rank;

    UnionFind(i64 n) : sz(n) {
        parent.assign(n, 0);
        REP(i, n) {
            parent[i] = i;
        }
        rank.assign(n, 1);
    }

    T find(T t) {
        if (parent[t] == t) return t;
        return parent[t] = find(parent[t]);
    }

    bool unite(T t1, T t2) {
        t1 = find(t1);
        t2 = find(t2);
        if (t1 == t2) return false;

        if (rank[t1] < rank[t2]) swap(t1, t2);
        parent[t2] = t1;
        rank[t1] += rank[t2];
        return true;
    }

    bool same(T t1, T t2) {
        return find(t1) == find(t2);
    }
};

using P = pair<i64, i64>;

int main() {
    i64 N, M; cin >> N >> M;
    vector<i64> A(N);
    REP(i, N) { cin >> A[i]; A[i]--; }

    UnionFind<i64> uf(N);
    REP(i, M) {
        i64 a, b; cin >> a >> b;
        a--; b--;
        uf.unite(a, b);
    }

    unordered_map<i64, set<i64>> scc;
    REP(i, N) {
        scc[uf.find(i)].insert(i);
    }

    i64 cnt = 0;
    REP(i, N) {
        if (scc[uf.find(i)].count(A[i]) > 0) cnt++;
    }
    cout << cnt << endl;

    return 0;
}