# 問題解決力を鍛える！アルゴリズムとデータ構造

## 第11章~

- 任意参加
- ファシリテーター: hsu

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所

>[name=hsu]

https://www.runoob.com/data-structures/union-find-size.html
文字を読んでも理解できずJavaの例を参考しにJSに
効率は木の高さに依存するなので時間複雑度はO(h)です

class UnionFind {
  constructor(n) {
    // parent[i] 表示第 i 個元素所指向的父節點
    this.parent = new Array(n);
    // 數據個數
    this.count = n;
    // 初始化, 每一個 parent[i] 指向自己, 表示每一個元素自己自成一個集合
    for (let i = 0; i < n; i++) {
      this.parent[i] = i;
    }
  }


  find(p) {
    if (p < 0 || p >= this.count) {
      throw new Error("Index out of range");
    }
    // Search self-parent node until achieving root node
    // root node: parent[p] === p
    while (p !== this.parent[p]) {
      p = this.parent[p];
    }
    return p;
  }

  // 要素pとqが同じ集合に属するかどうかを判断し、それらのルートノードが同じかどうかを確認します
  isConnected(p, q) {
    return this.find(p) === this.find(q);
  }

  // 要素pとqが属する2つの集合をマージする
  unionElements(p, q) {
    const pRoot = this.find(p);
    const qRoot = this.find(q);
    if (pRoot === qRoot) {
      return;
    }
    this.parent[pRoot] = qRoot;
  }
}

size化にすると効率が上がる

class UnionFindWithSizeOptimization {
  constructor(n) {
    // parent[i] 表示第 i 個元素所指向的父節點
    this.parent = new Array(n);
    // sz[i] 表示以 i 為根的集合中元素個数
    this.sz = new Array(n);
    // 數據個數
    this.count = n;
    // 初始化, 每一個 parent[i] 指向自己, 表示每一個元素自己自成一個集合
    for (let i = 0; i < n; i++) {
      this.parent[i] = i;
      this.sz[i] = 1;
    }
  }


  find(p) {
    if (p < 0 || p >= this.count) {
      throw new Error("Index out of range");
    }
    // Search self-parent node until achieving root node
    // root node: parent[p] === p
    while (p !== this.parent[p]) {
      p = this.parent[p];
    }
    return p;
  }

  // 要素pとqが同じ集合に属するかどうかを判断し、それらのルートノードが同じかどうかを確認します
  isConnected(p, q) {
    return this.find(p) === this.find(q);
  }

  // 要素pとqが属する2つの集合をマージする
  unionElements(p, q) {
    const pRoot = this.find(p);
    const qRoot = this.find(q);
    if (pRoot === qRoot) {
      return;
    }
    
    // 少ない集合は多いの方にマージする
    if (this.sz[pRoot] < this.sz[qRoot]) {
      this.parent[pRoot] = qRoot;
      this.sz[qRoot] += this.sz[pRoot];
    } else {
      this.parent[qRoot] = pRoot;
      this.sz[pRoot] += this.sz[qRoot];
    }
  }
}

テストしたBeforeとAfter

function testUF(uf, m) {
  const startTime = new Date().getTime();
  const n = uf.count;
  for (let i = 0; i < m; i++) {
    const a = Math.floor(Math.random() * n);
    const b = Math.floor(Math.random() * n);
    uf.unionElements(a, b);
  }
    
  for (let i = 0; i < m; i++) {
    const a = Math.floor(Math.random() * n);
    const b = Math.floor(Math.random() * n);
    uf.isConnected(a, b);
  }
 
  const endTime = new Date().getTime();
  return (endTime - startTime) / 1000;
}

const n = 100000;
const m = 100000;

const uf1 = new UnionFind(n);
console.log(`Without optimization: ${testUF(uf1, m)} s`);

const uf2 = new UnionFindWithSizeOptimization(n);
console.log(`With optimization: ${testUF(uf2, m)} s`);

Without optimization: 0.380 s
With optimization: 0.064 s

> [name=tsujita]

- 特段語れることがないのですが・・・・
- こちらのサイト内のスライドがわかりやすかったです
https://atcoder.jp/contests/atc001/tasks/unionfind_a
- まとめて→同じグループにいるか判定するプロセス　の中で計算をより効率的にできる手法と理解しました

> [name=teruya]

https://atcoder.jp/ranking
https://atcoder.jp/contests/arc032/tasks/arc032_2

# 上位ノードほど @rank が大きい数字となる
class Node
  attr_accessor :parent, :rank

  # 親は自分自身、ランクは 0 として初期化する
  def initialize(n)
    @parent = n
    @rank = 0
  end
end

class UnionFind
  # 0 から n までのノード（つまりn + 1個）を初期化する
  def initialize(n)
    @nodes = (0..n).map { |i| Node.new(i) }
  end

  # 再帰で最も上位の親を探して更新し、その値を返す
  def parent(x)
    return x if @nodes[x].parent == x
    return @nodes[x].parent = parent(@nodes[x].parent)
  end

  # a と b を仲間にする
  def unite(a, b)
    a_parent = parent(a)
    b_parent = parent(b)
    # a 及び b の親が同じ場合は何もしない
    return if a_parent == b_parent

    # a親ランク < b親ランク の場合は、b親をa親の親とする
    # なお、ランクをいじる必要はなし
    if @nodes[a_parent].rank < @nodes[b_parent].rank
      @nodes[a_parent].parent = b_parent
    # その他の場合は、a親をb親の親とする
    else
      @nodes[b_parent].parent = a_parent
    # a親、及びb親のランクが同じ場合は、a親のランクを +1 する
      @nodes[a_parent].rank += 1 if @nodes[a_parent].rank == @nodes[b_parent].rank
    end
  end

  # a と b の親が同じかどうかを返す
  def same?(a, b)
    parent(a) == parent(b)
  end

  # 各ノードの親を全て出力する確認用
  def parents
    @nodes.map(&:parent)
  end
end

## 振り返り

> [name=tsujita]

たまーにatcoderで照屋さんの過去の解答例を見つけてます

> [name=chen]

都市の例は面白い...
それで説明すれば理解しやすいですねw

> [name=hsu]

atcoder見てみます

> [name=teruya]

たまにアルゴリズムで殴って問題解決してます
https://github.com/Catal/Nozomi/pull/8263 など

## 終了後ファシリテーターがやること

- 次回のファシリテーターを決める
- chenさん
- 読む範囲を決める
- 第12.1~12.4章