2017-05-18

【AOJ ALDS1_8】C: Binary search trees - Binary Search Tree III

問題

二分探索木削除 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

二分探索木の削除を実装する問題
削除するノードを以下の3つの条件で場合分けし処理を行う.
1. 子ノードを持たない
2. 子ノードを1つだけ持つ
3. 子ノードを2つ持つ
1, 2の場合は対象ノードを取り除くだけで良い.（取り除いてその子ノードを親ノードに繋げば良い）
3の場合は, 右部分木の最小ノードを削除したいノードに置き換える.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

struct Node{
  int data;
  Node *parent, *left, *right;
};

Node *root;

Node* findNode(int x){
  Node *r = root;
  while(r != NULL && r->data != x){
    if(x < r->data){
      r = r->left;
    }else{
      r = r->right;
    }    
  }
  return r;
}

Node* getMinNode(Node *u){
  while(u->left != NULL) u = u->left;
  return u;
}

Node* getSuccessor(Node *u){
  if(u->right != NULL) return getMinNode(u->right);
  Node *p = u->parent;
  while(p != NULL && p->right == u){
    u = p;
    p = p->parent;
  }
  return p;
}

void deleteNode(Node *u){
  Node *target;
  Node *child;

  // 削除対象ノードを決める
  // 子ノードが無い or 1個だけの場合, 削除対象ノードはuそのもの
  // 子が２つある場合, uの次接点となる.
  if(u->left == NULL || u->right == NULL){ // 子ノードがない or 1個
    target = u;
  }else{
    target = getSuccessor(u);
  }
  
  // 削除対象ノードの子ノードを求める
  if(target->left != NULL){
    child = target->left;
  }else{
    child = target->right;
  }

  // 子ノードがある場合, 子ノードの親ノードを削除対象ノードの親ノードにする
  if(child != NULL){
    child->parent = target->parent;
  }

  // 左 or 右のノードに子ノードを格納
  if(target->parent == NULL){
    root = child;    
  }else{
    if(target == target->parent->left){
      target->parent->left = child;
    }else{
      target->parent->right = child;
    }
  }
  
  // 削除対象が異なる場合はdataを入れ替え
  if(target != u) u->data = target->data;
  free(target);  
}

void insertNode(int x){
  Node *root_tmp = root;
  Node *elem;

  elem = (Node *)malloc(sizeof(Node));
  elem->data = x;
  elem->left = NULL;
  elem->right = NULL;
  
  Node *prev = NULL;

  while(root_tmp != NULL){
    prev = root_tmp;
    if(elem->data < root_tmp->data){
      root_tmp = root_tmp->left;
    }else{
      root_tmp = root_tmp->right;
    }
  }

  elem->parent = prev;

  if(elem->parent == NULL){
    root = elem;
  }else{
    if(elem->parent->data < elem->data){
      elem->parent->right = elem;
    }else{
      elem->parent->left = elem;
    }
  }
}

// 先行巡回
void preorder(Node *u){
  if(u == NULL) return; 
  cout << " " << u->data;
  preorder(u->left);
  preorder(u->right);
}

// 中間巡回
void inorder(Node *u){
  if(u == NULL) return; 
  inorder(u->left);
  cout << " " << u->data;
  inorder(u->right);
}

signed main(){
  int n;
  string command;
  int elem;

  cin >> n;
  rep(i, n){
    cin >> command;
    if(command == "insert"){
      cin >> elem;
      insertNode(elem);
    }else if(command == "find"){
      cin >> elem;
      if(findNode(elem)!=NULL) cout << "yes" << endl;
      else cout << "no" << endl;
    }else if(command == "delete"){
      cin >> elem;
      deleteNode(findNode(elem));
    }else{
      inorder(root);
      cout << "\n";
      preorder(root);
      cout << "\n";
    }
  }
}

参考

PDFです.
http://f-server.ics.kagoshima-u.ac.jp/~fuchida/algorithm/alg10-二分探索木.pdf

2017-05-18

【AOJ ALDS1_8】B: Binary search trees - Binary Search Tree II

AOJ プログラミング

問題

二分探索木検索 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

二分探索木の探索を行う問題
二分探索木の構築(insert)自体は前回のものを流用

muttan1203.hatenablog.com

関数findは, カレントノードがNULLになるまでループし, 値が見つかったらtrueを返し見つからない場合はfalseを返せば良い.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
 
using namespace std;
 
struct Node{
  int data;
  Node *parent, *left, *right;
};
 
Node *root;
 
bool find(int x){
  Node *r = root;
  while(r != NULL){    
    if(r->data == x){
      return true;
    }else if(x < r->data){
      r = r->left;
    }else{
      r = r->right;
    }    
  }
  return false;
}
 
void insert(int x){
  Node *root_tmp = root;
  Node *elem;
 
  elem = (Node *)malloc(sizeof(Node));
  elem->data = x;
  elem->left = NULL;
  elem->right = NULL;
   
  Node *prev = NULL;
 
  while(root_tmp != NULL){
    prev = root_tmp;
    if(elem->data < root_tmp->data){
      root_tmp = root_tmp->left;
    }else{
      root_tmp = root_tmp->right;
    }
  }
 
  elem->parent = prev;
 
  if(elem->parent == NULL){
    root = elem;
  }else{
    if(elem->parent->data < elem->data){
      elem->parent->right = elem;
    }else{
      elem->parent->left = elem;
    }
  }
}
 
void preorder(Node *u){
  if(u == NULL) return; 
  cout << " " << u->data;
  preorder(u->left);
  preorder(u->right);
}
 
void inorder(Node *u){
  if(u == NULL) return; 
  inorder(u->left);
  cout << " " << u->data;
  inorder(u->right);
}
 
signed main(){
  int n;
  string command;
  int elem;
 
  cin >> n;
  rep(i, n){
    cin >> command;
    if(command == "insert"){
      cin >> elem;
      insert(elem);
    }else if(command == "find"){
      cin >> elem;
      if(find(elem)) cout << "yes" << endl;
      else cout << "no" << endl;
    }else{
      inorder(root);
      cout << "\n";
      preorder(root);
      cout << "\n";
    }
  }
}

2017-05-17

【AOJ ALDS1_8】A: Binary search trees - Binary Search Tree I

AOJ プログラミング

問題

二分探索木挿入| アルゴリズムとデータ構造 | Aizu Online Judge

方針

二分探索木を生成する問題
ある節点xの左部分木に属する節点をy1, 右部分木に属する節点をy2としたとき, y1のキー ${\leq}$ xのキーかつ xのキー ${\leq}$ y2のキーを満たすものである.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
#define INF 1e9

using namespace std;

struct Node{
  int data;
  Node *parent, *left, *right;
};

Node *root;

void insert(int x){
  Node *root_tmp = root;
  Node *elem;

  elem = (Node *)malloc(sizeof(Node));
  elem->data = x;
  elem->left = NULL;
  elem->right = NULL;
  
  Node *prev = NULL;

  while(root_tmp != NULL){
    prev = root_tmp;
    if(elem->data < root_tmp->data){
      root_tmp = root_tmp->left;
    }else{
      root_tmp = root_tmp->right;
    }
  }

  elem->parent = prev;

  if(elem->parent == NULL){
    root = elem;
  }else{
    if(elem->parent->data < elem->data){
      elem->parent->right = elem;
    }else{
      elem->parent->left = elem;
    }
  }
}

void preorder(Node *u){
  if(u == NULL) return; 
  cout << " " << u->data;
  preorder(u->left);
  preorder(u->right);
}

void inorder(Node *u){
  if(u == NULL) return; 
  inorder(u->left);
  cout << " " << u->data;
  inorder(u->right);
}

signed main(){
  int n;
  string command;
  int elem;

  cin >> n;
  rep(i, n){
    cin >> command;
    if(command == "insert"){
      cin >> elem;
      insert(elem);
    }else{
      inorder(root);
      cout << "\n";
      preorder(root);
      cout << "\n";
    }
  }
}

2017-05-17

【AOJ ALDS1_12】A: Graph II - Minimum Spanning Tree

AOJ プログラミング

問題

最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge

方針

最小全域木(Minimum Spanning Tree)を作ろう.
全域木は閉路を持たない木(でいいのだろうか)
最小全域木は, 辺のコストの和が最も小さくなる全域木のこと.
頂点数が ${0 \leq n \leq 100}$ であることから, プリムのアルゴリズムを利用してMSTを求める.
プリム法は, 以下のようなアルゴリズムである.
1. 任意の頂点rを選び, Tに追加する.
2. MSTに属する頂点の集合をT, グラフGの頂点の集合をVとする.
3. Tに属する頂点とV-Tに属する頂点を繋ぐ辺の中で, コストが一番小さいノードuを選びそれをMSTの辺とする.
4. uをTに追加する.
5. これをV=Tとなるまで(2)から(4)を繰り返す.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define INF 1e9
#define N_MAX 100

using namespace std;

// 隣接行列
int G[N_MAX][N_MAX];

// d[i] := 頂点iからMSTの集合Tまでの最短距離
int d[N_MAX];

// 確定したノード
bool visited[N_MAX];

// 親ノード
int p[N_MAX];

void init(){
  rep(i, N_MAX){
    d[i] = INF;
    visited[i] = false;
    p[i] = -1;
  }
}


int prim(int n){
  init();
  
  // 始点は0
  d[0] = 0;
  
  while(true){
    int u = -1;
    int _min = INF;

    // 最短距離で行けるノードuを確定
    rep(i, n){
      if(d[i] < _min && !visited[i]){
        u = i;
        _min = d[i];
      }
    }

    if(u == -1) break;
    
    visited[u] = true;

    // ノードuから行けるノードの最短距離を更新
    rep(v, n){
      if(G[u][v] != -1 && !visited[v] && G[u][v] < d[v]){
        d[v] = G[u][v];
        p[v] = u;
      }
    }
  }

  int sum = 0;
  rep(i, n){
    if(visited[i]){
      sum += G[i][p[i]];
    }
  }

  return sum;
}

signed main(){
  int n;
  cin >> n;
  rep(i, n){
    rep(j, n){
      cin >> G[i][j];
    }
  }

  cout << prim(n) << endl;
  
}

ところで確定したノード適当にvisitedにしちゃったんですけどこれvisitじゃ色々おかしい気がする.

2017-05-16

【AOJ ALDS1_11】D: Graph I - Connected Components

AOJ プログラミング

問題

グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

グラフの連結成分(Connected Components)を求める問題.
連結成分とは, 必ずしも連結でないグラフGに対して, その極大連結部分グラフのことをグラフGの連結成分という.
G'がGの極大連結部分グラフであるとは, 1) G'がGの部分連結グラフであること 2) G'を部分グラフとして持つようなGの連結部分グラフが存在しないことが満たされているものを言う.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<stack>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
#define MAX_N 100001

using namespace std;

vector<int> G[MAX_N];
int label[MAX_N];

void dfs(int start, int id){
  stack<int> s;
  s.push(start);
  label[start] = id;
  while(!s.empty()){
    int u = s.top(); s.pop();
    rep(i, G[u].size()){
      int v = G[u][i];
      if(label[v] == -1){
    label[v] = id;
    s.push(v);
      }
    }
  }
}

void solve(int n){
  int id = 1;

  rep(u, n){
    if(label[u] == -1){
      dfs(u, id);
      id++;
    }   
  }
}

void init(){
  rep(i, MAX_N) label[i] = -1;
}

signed main(){
  int n, m, s, t;
  cin >> n >> m;
  rep(i, m){
    cin >> s >> t;
    G[s].pb(t);
    G[t].pb(s);
  }

  init();
  solve(n);

  int q;

  cin >> q;
  rep(i, q){
    cin >> s >> t;
    if(label[s] == label[t]){
      cout << "yes" << endl;
    }else{
      cout << "no" << endl;
    }
  }
}

風邪を引きながら理解するのは無理があった.

参考

http://coconut.sys.eng.shizuoka.ac.jp/gn/04/handout6.pdf

http://dopal.cs.uec.ac.jp/okamotoy/lect/2012/graphtheory/lect10.pdf

2017-05-15

【AOJ ALDS1_6】C: Sort II - Quick Sort

AOJ プログラミング

問題

Quick Sort | Aizu Online Judge

方針

クイックソートは ${O(n log{n})}$ の高速なソートであるが, すべての要素がすでに整列済みの場合など最悪の計算量は ${O(n^2)}$ である.
それを解するため, しきい値(pivot)をランダムに取る, データ列の中央値を取るなどの工夫が必要.
分割統治法に基づいたアルゴリズムであるが, マージソートと違いインプレースソートである.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define INF 1e9
#define MAX_N 100001

using namespace std;

struct Card{
  char c;
  int num;
};

int n;
Card A[100001], B[100001];
int comp;
Card l[MAX_N/2+2];
Card r[MAX_N/2+2];

void merge(int left, int right, int mid){
  rep(i, mid-left){
    l[i] = B[left + i];
  }
  rep(i, right-mid){
    r[i] = B[mid + i];
  }

  l[mid-left].num = r[right-mid].num = INF;
  
  int left_idx, right_idx;
  left_idx = right_idx = 0;
  REP(i,left,right){
    comp++;
    if(l[left_idx].num <= r[right_idx].num){
      B[i] = l[left_idx];
      left_idx++;
    }else{
      B[i] = r[right_idx];
      right_idx++;
    }
  }
}

void mergeSort(int left, int right){
  if(right - left > 1){
    int mid = (right + left)/2;
    mergeSort(left, mid);     // 左
    mergeSort(mid, right);    // 右
    merge(left, right, mid);  // マージ
  }
}

int partition(int p, int r){
  int i;
  i = p-1;
  REP(j, p, r){
    if(A[j].num <= A[r].num){
      i++;
      swap(A[i], A[j]);
    }
  }
  swap(A[i+1], A[r]);
  
  return i+1;
}

void quickSort(int p, int r){
  if(r - p > 0){
    int ret = partition(p, r);
    quickSort(p, ret-1);
    quickSort(ret+1, r);
  }
}

bool compare(Card l, Card r){
  return (l.num <= r.num);
}

signed main(){

  cin >> n;
  rep(i, n){
    cin >> A[i].c >> A[i].num;    
    B[i].c = A[i].c;
    B[i].num = A[i].num;
  }
  
  quickSort(0, n-1);
  mergeSort(0, n);

  bool flag = false;
  rep(i, n){
    if(A[i].c != B[i].c) flag = true;
  }
  
  if(flag) cout << "Not stable" << endl;
  else cout << "Stable" << endl;

  rep(i, n){
    cout << A[i].c << " " << A[i].num << endl;
  }

}

2017-05-15

【AOJ ALDS1_6】B : Sort II - Partition

AOJ プログラミング

問題

パーティション | アルゴリズムとデータ構造 | Aizu Online Judge

方針

iをA[r]以下の数が格納されている終端を示す変数とする.
jをpからr-1まで進めていき, A[j]がxより大きければそのまま, x以下の場合はiを1つ進めてスワップする.
最後にi+1とr番目の要素をスワップし, i+1を返す.

コード

#include <bits/stdc++.h>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int A[100001];

int partition(int p, int r){
  int i;
  i = p-1;

  REP(j, p, r){
    if(A[j] <= A[r]){
      i++;
      swap(A[i], A[j]);
    }
  }
  swap(A[i+1], A[r]);
  
  return i+1;
}


signed main(){
  int n;
  cin >> n;
  rep(i, n){
    cin >> A[i];
  }

  int ret = partition(0, n-1);
  
  rep(i, n){    
    if(i > 0) cout << " ";
    if(ret == i){
      cout << "[" << A[i] << "]";
    }else{
      cout << A[i];
    }
  }
  puts("");
}

先週末出かけてて何もできなかったので今週は頑張ろう.

日々精進

aikoと旅行とプログラミング

【AOJ ALDS1_8】C: Binary search trees - Binary Search Tree III

問題

方針

コード

参考

【AOJ ALDS1_8】B: Binary search trees - Binary Search Tree II

問題

方針

コード

【AOJ ALDS1_8】A: Binary search trees - Binary Search Tree I

問題

方針

コード

【AOJ ALDS1_12】A: Graph II - Minimum Spanning Tree

問題

方針

コード

【AOJ ALDS1_11】D: Graph I - Connected Components

問題

方針

コード

参考

【AOJ ALDS1_6】C: Sort II - Quick Sort

問題

方針

コード

【AOJ ALDS1_6】B : Sort II - Partition

問題

方針

コード