ARC 097 D Equals

問題

見た感じ

スワップできる数字の組が例えば(1,2)(2,3)だとしたら、このスワップを組み合わせて、p[1],p[2],p[3]を好きな順番にならべ変えることができて、おそらく要素数が増えたとしても同じように、好きな順番に挿入していけそう。
だから、重要なのはこの数字の組でどれだけの数字がグループになっているかで並び方は関係ない。
例えば{(1,3),(3,6)}がスワップできる数字の組だとすると
最初に与えられたpの{p[1],p[3],p[6]}に1が含まれていれば、スワップによって好きな順番に並べられるので、p[1]=1とすることができるし、もし含まれなければ絶対に無理。
だから、スワップできる数字のグループを持っていて、数字同士が同じグループにいるかが早く判定できればよいので、union-find treeを使って実装した。

解法

union-find tree 上でスワップ可能な数字の組をmergeしていって、最後に各iについて、iとp[i]が同じグループに入っているかどうかを調べ、入っていれば、ansを1増やしていった。

ソースコード

struct uftree{
    int n;
    int cou;
    vector<int> parent;
    vector<int> rank;
    vector<int> _size;
    uftree(int n):n(n){
        parent=vector<int>(n);
        rank=vector<int>(n,0);
        _size=vector<int>(n,1);
        cou=n;
        rep(i,n){
            parent[i]=i;
        }
    }
    int root(int i){
        return parent[i]==i?i:parent[i]=root(parent[i]);
    } 
    bool same(int i,int j){
        return root(i)==root(j);
    }
    void merge(int i,int j){
        i=root(i);j=root(j);
        if(i==j)return;
        cou--;
        if(rank[i]>=rank[j]){
            parent[j]=i;
            _size[i]+=_size[j];
        }else{
            parent[i]=j;
            _size[j]+=_size[i];
        }
        if(rank[i]==rank[j])rank[i]++;
        return;
    }
    int count(){
        return cou;
    }
    int unitsize(int i){
        return _size[root(i)];
    }
};
const int N_MAX=100005;
int n,m,p[N_MAX];

int main(){
    int x,y;
    //入力
    cin>>n>>m;
    rep(i,n)cin>>p[i];
    uftree tree(n);
    rep(i,m){
        cin>>x>>y;
        tree.merge(x-1,y-1);
    }
    //処理
    int ans=0;
    rep(i,n){
        if(tree.same(p[i]-1,i))ans++;
    }
    //出力
    cout << ans <<endl;
}

振り返り

unionfind tree が生き生きしてるのは初めてだった