CODE THANKS FESTIVAL 2017 H - Union Sets

thanksのHを複数の解法で解いてみた話

解法1

公式で解説されていたLCAを使った解法
t回目のクエリではじめて頂点p, qがつながれたとき、頂点p, qを重みtの辺でつないだ森をつくる。これはunionfindを用いて、頂点p, qがすでにつながれていなければ新たに辺でつなぐとすることでできる。

パス(p, q)上で最も大きい辺の重みを高速に求めることを考えるとこれはLCAを使うとできる。
ダブリングを用いたLCAでは parent[k][v] = (頂点vから2^k回親をたどったときの頂点) を構築しLCAを求めるが、同様に (頂点vから2^k回親をたどったときの最大の重み) の情報を前計算しておくことで最大の重みを求めることが出来る。

LCAの実装が怪しい気がするけど通ったのでセーフ

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAX_N 100010

class UnionFind {
private:
  // 親と木の深さ
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
  bool used[MAX_N];
public:
  UnionFind();
  UnionFind(int);
  int find(int x);
  void unite(int, int);
  bool same(int, int);
  int size(int);
  int group(int);
};

//MAX_Nで初期化
UnionFind::UnionFind() {
  for(int i=0; i<MAX_N; ++i) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素数nで初期化
UnionFind::UnionFind(int n) {
  for(int i=0; i<n; i++) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素xの親を求める
int UnionFind::find(int x) {
  if(par[x] == x) return x;
  else return par[x] = find(par[x]);
}

// xとyの属する集合を併合
void UnionFind::unite(int x, int y) {
  // xとyの親
  x = find(x);
  y = find(y);
  if(x == y) return;

  // yのほうが深さが深い　xの親はyの親
  if(rank[x] < rank[y]) {
    par[x] = y;
    s[y] = s[x] + s[y];
  }
  else {
    par[y] = x;
    s[x] = s[x] + s[y];
    if( rank[x] == rank[y] ) rank[x]++;
  }
}

// xの属する連結成分のサイズ
int UnionFind::size(int x) { return s[find(x)];}

// xとyが同じ集合に属するか
bool UnionFind::same(int x, int y) { return find(x) == find(y);}

// 連結成分数
int UnionFind::group(int n) {
  REP(i, n) used[find(i)] = true;
  int ret = 0;
  REP(i, n) if(used[i]) ret++;
  return ret;
}

UnionFind uf;

#define MAX_LOG_N 50

vector<PII> G[MAX_N];  //グラフの隣接リスト
int root = 0;     //根のノード

PII parent[MAX_LOG_N][MAX_N];
int depth[MAX_N];
bool used[MAX_N];

void dfs(int v, int p, int d, int w) {
  // cout << v << " " << p << " " << d << " " << w << endl;
  used[v] = true;
  // 頂点pと頂点vの辺の重み
  parent[0][v] = {p, w};
  depth[v] = d;
  REP(i, G[v].size()) if(G[v][i].first != p) dfs(G[v][i].first, v, d+1, G[v][i].second);
}

//初期化 O(logn)
void init(int n) {
  REP(i, n) {
    if(!used[i]) {
      // cout << i << endl;
      dfs(i, -1, 0, -1);
    }
  }
  REP(k, MAX_LOG_N-1) REP(v, n) {
    if(parent[k][v].first < 0) parent[k+1][v] = parent[k][v];
    else {
      PII tmp = parent[k][parent[k][v].first];
      parent[k+1][v] = {tmp.first, max(parent[k][v].second, tmp.second)};
    }
  }
}

// uとvのlcaを求める
int lca(int u, int v) {
  if(depth[u] > depth[v]) swap(u, v);
  int ret = 0;
  REP(k, MAX_LOG_N) {
    if((depth[v]-depth[u]) >> k & 1) {
      chmax(ret, parent[k][v].second);
      v = parent[k][v].first;
    }
  }
  if(u == v) return ret;
  for(int k = MAX_LOG_N-1; k>=0; k--) {
    if(parent[k][u] != parent[k][v]) {
      chmax(ret, parent[k][u].second);
      chmax(ret, parent[k][v].second);
      u = parent[k][u].first;
      v = parent[k][v].first;
    }
  }
  return ret;
}

signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    if(!uf.same(a, b)) {
      uf.unite(a, b);
      G[a].PB({b, i+1});
      G[b].PB({a, i+1});
    }
  }

  init(n);
  int q;
  cin >> q;
  REP(i, q) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    if(!uf.same(x, y)) cout << -1 << endl;
    else {
      int ret = lca(x, y);
      cout << ret << endl;
    }
  }

  return 0;
}

解法2

並列ニ分探索を使った解法
並列二分探索についてはAGC002-Dの解説放送を見るのがおすすめです。
まず、クエリが1個のとき二分探索で答えを求めることを考える。「X回目まで頂点の併合をしたとき、クエリで指定された頂点が連結であるかどうか」という質問を考えると1回連結になればそれ以降はずっと連結なので単調性があり二分探索ができる。頂点の併合はO(Mα(N))でできるのでクエリ1つに対してはO(Mα(N)logM)でできる。
クエリはQ個あるためQ個バラバラに上記の二分探索を行うと当然TLEする。そこでQ個並列に二分探索をすることで2sec以内に計算することができる。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
  bool used[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]) {
      par[x] = y; s[y] = s[x] + s[y];
    } else {
      par[y] = x; s[x] = s[x] + s[y];
      if( rank[x] == rank[y] ) rank[x]++;
    }
  }
  int size(int x) { return s[find(x)];}
  bool same(int x, int y) { return find(x) == find(y);}
  int group(int n) {
    REP(i, n) used[find(i)] = true;
    int ret = 0;
    REP(i, n) if(used[i]) ret++;
    return ret;
  }
};
UnionFind uf;

struct query_{
  int piv,z,x,y;
  int lb,ub;
  int idx;
  bool operator<(const query_& a){ return piv<a.piv; }
};
query_ query[100010];

int a[100010], b[100010];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
  }
  int q;
  cin >> q;
  REP(i, q) {
    cin >> query[i].x >> query[i].y;
    query[i].x--, query[i].y--;
    query[i].lb = -1;
    query[i].ub = m;
    query[i].piv = (m-1)/2;
    query[i].idx = i;
  }

  sort(query, query+q);
  REP(_, 20) {
    uf.init(n);
    int idx = 0;
    REP(i, m) {
      // i番目について処理
      uf.unite(a[i], b[i]);
      while(idx < q && query[idx].piv==i) {
        if(query[idx].ub-query[idx].lb <= 1) {
          query[idx].piv = query[idx].ub;
          idx++;
          continue;
        }
        // query[idx].pivで二分探索の条件判定
        if(uf.same(query[idx].x, query[idx].y)) query[idx].ub = i;
        else query[idx].lb = i;
        query[idx].piv = max(0LL, (query[idx].lb + query[idx].ub)/2);
        idx++;
      }
    }
    sort(query, query+q);
  }

  VI res(q);
  REP(i, q) {
    if(uf.same(query[i].x, query[i].y)) res[query[i].idx] = query[i].ub;
    else res[query[i].idx] = -2;
  }
  REP(i, q) cout << res[i]+1 << endl;

  return 0;
}

解法3

部分永続unionfindを使う
やぶについて書きますを参考に部分永続unionfindを実装する。
find(x, t):t回目のクエリ以前で頂点xの親を求める O(logN)
unite(x, y):頂点x,yを併合 O(logN)

部分永続unionfindを構築しておくと、解法2と違い二分探索で辺を張る必要がないためクエリ1つあたりO(log(N+M))で解くことができ、全体でO(Qlog(M+N))で解ける。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// find:O(logN) unite:O(logN)
class persistentUF {
public:
  const static int MAX_N = 100010;
  unordered_map<int, int> par[MAX_N];
  int rank[MAX_N];
  int fin[MAX_N];
  int idx;

  persistentUF() { init(); }
  void init() {
    idx = 0;
    REP(i, MAX_N) par[i][0] = i, rank[i] = 1, fin[i] = 0;
  }
  persistentUF(int n) { init(n); }
  void init(int n) {
    idx = 0;
    REP(i, n) par[i][0] = i, rank[i] = 1, fin[i] = 0;
  }

  int find(int x, int t) {
    if(t >= fin[x] && par[x][fin[x]] != x) return find(par[x][fin[x]], t);
    return x;
  }

  void unite(int x, int y) {
    x = find(x, idx);
    y = find(y, idx);
    idx++;
    if(x == y) return;
    if(rank[x] < rank[y]) par[x][idx] = y, fin[x] = idx;
    else {
      par[y][idx] = x, fin[y] = idx;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

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

signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    uf.unite(a, b);
  }

  int q;
  cin >> q;
  REP(i, q) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    if(uf.find(x, m) != uf.find(y, m)) {
      cout << -1 << endl;
      continue;
    }
    int lb = -1, ub = m;
    while(ub-lb > 1) {
      int mid = (ub+lb)/2;
      if(uf.find(x, mid) == uf.find(y, mid)) ub = mid;
      else lb = mid;
    }
    cout << ub << endl;
  }

  return 0;
}

あとデータ構造をマージする一般的なテクで解けるらしいが理解できなかったのでできたら書く。

ferinの競プロ帳

競プロについてのメモ

CODE THANKS FESTIVAL 2017 H - Union Sets

解法1

解法2

解法3