ABC097 D Equals を解いた話

最近更新できていないので、競プロネタを投稿。

下記の問題を解説ACした。 D - Equals

問題

整数x [1, N]を適当に並び替えた順列p_1, p_2, ..., p_NとM個の整数ペア(x_1, y_2), ..., (x_M, y_M)が与えられる。
与えられた整数ペアを用いて、 swap(p_x, p_y)を何度でも行えるとする。
操作後にp_i = i となる数の最大数を求めよ。

要はインデックス通りに並べられることが可能な数字の最大の数を求める?ということ。
自力ではACできずにUnionFindの解法を参考にした。

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

素集合データ構造で、同じグループに属す(Union)操作と同じグループかを探す(Find)操作を行うものである。
素集合というのは、ある要素が複数の集合に含まれないものを指すらしい。

コードはこんな感じになった。
x,yの配列いらないしメモリ無駄にしてるけど、とりあえずこれで提出してAC:

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
using ll = long long;

template <typename T>
class UnionFind {
public:
  T n;
  vector <T> d;
  UnionFind(T n) :d(n, -1) {} 
  int find(T x){
    if(d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(T x, T y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    if(size(x) < size(y)) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  int size(T v){ return -d[find(v)];}
  bool same(T x, T y){
    return find(x) == find(y);
  }
};

int p[1000000], x[1000000], y[1000000];

int
main(void){  
  ios_base::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  REP(i, n) cin >> p[i];
  REP(i, m) cin >> x[i] >> y[i];

  UnionFind<int> uf = UnionFind<int>(n+1);

  REP(i, m) uf.unite(x[i], y[i]);

  ll ans = 0LL;

  REP(i, n) if(uf.same(i+1, p[i])) ans++; 

  cout << ans << endl;
  
  //if(uf.unite(x[0], y[0])) cout << "success" << endl;
  //cout << uf.size(5) << endl;;
  
  return 0;
}