日々精進

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

【AOJ ALDS1_11】D: Graph I - Connected Components

問題

グラフの連結成分 | アルゴリズムとデータ構造 | 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

【AOJ ALDS1_6】C: Sort II - Quick Sort

問題

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;
  }

}

【AOJ ALDS1_6】B : Sort II - Partition

問題

パーティション | アルゴリズムとデータ構造 | 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("");
}

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

【AOJ ALDS1_13】A: Heuristic Search - 8 Queens Problem

問題

| アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • バックトラック法を用いて探索を行おう.

コード

#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 N 8

using namespace std;

bool isLocated[N][N];
int row[N];     // 行方向の襲撃
int col[N];     // 列方向の襲撃
int dl[2*N-1];  // 左下への襲撃
int dr[2*N-1];  // 右下への襲撃

void print(){
  rep(i, N){
    rep(j, N){
      if(isLocated[i][j] && row[i] != j) return;
    }
  }

  rep(i, N){
    rep(j, N){
      cout << (row[i] == j?"Q":".");
    }
    cout << "\n";
  }
}

void solve(int i){

  // すべての行置き終わった
  if(i == N){
    print();
    return;
  }

  // すべての列試す
  rep(j, N){
    // すでに襲撃されている場合
    if(col[j] == 1 || dl[j + i] == 1 || dr[i - j + N - 1] == 1){
      continue;
    }
    
    // i行目のj列にコマを置く(i列目はj列目のコマに襲撃されている)
    row[i] = j;
    // j行目, 左下方向, 右下方向にフラグを立てる.
    col[j] = dl[j+i] = dr[i-j+N-1] = 1;
    // i+1行目を探索
    solve(i+1);
    // フラグを解除する
    col[j] = dl[j+i] = dr[i-j+N-1] = -1;
  }
  
}

void init(){
  rep(i, N){
    row[i] = col[i] = -1;    
  }

  rep(i, 2*N-1){
    dl[i] = dr[i] = -1;
  }

  rep(i, N){
    rep(j, N){
      isLocated[i][j] = false;
    }
  }
}

signed main(){
  int n;
  int r, c;

  init();
  cin >> n;
  rep(i, n){
    cin >> r >> c;
    isLocated[r][c] = true;
  }
  solve(0);  
}

なんかバグらせまくって辛かった.

【AOJ ALDS1_7】D: Tree - Reconstruction of a Tree

問題

木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • inorderを先頭から見ていったとき, その値をcとする.
  • そのcの位置をpreorderの中から探し, その値をmとする.
  • prem[m]より左側の値はcを根とする木の左部分木, 右側は右部分木となる.
  • それを再帰的に定義していく.
  • n = 5
  • pre = {1, 2, 3, 4, 5}
  • in = {3, 2, 4, 1, 5}
    最初の根は1(pre[0])となり, 左部分木は[3, 2, 4], 右部分木は[5]となる.
    左部分木の[3, 2, 4]のうち根は2(pre[1])となり, 左部分木は[3], 右部分木は[4]である.
    左部分木が終わったので根が1の木の右部分木となるが, 要素数が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++)
#define pb push_back
 
using namespace std;
 
vector<int> pre, in, ans;
int n;
int pos;
 
 
void solve(int l, int r){
  if(l - r >= 0) return;
  int root = pre[pos];
  pos++;
  int d = distance(in.begin(), find(in.begin(), in.end(), root));
  solve(l, d);
  solve(d+1, r);
  ans.pb(root);
}
 
signed main(){
 
  cin >> n;
   
  int m;
  rep(i,n){
    cin >> m;
    pre.pb(m);
  }
  rep(i,n){
    cin >> m;
    in.pb(m);    
  }
 
  solve(0, pre.size());
 
  cout << ans[0];
  REP(i,1, n){
    cout << " " << ans[i];
  }
  cout << "\n";
   
}

全く問題とは関係ないことだが, 初めてdistanceとfindを使った. distanceに至っては存在すら知らなかった. 猛省.

【AOJ ALDS1_7】C: Tree - Tree Walk

問題

Tree Walk | Aizu Online Judge

方針

  • 二分木を実装する.
  • 行きかけ順(Preorder Tree Walk), 通りかけ順(Inorder Tree Walk), 帰りがけ順(Postorder Tree Walk)を実装する.
  • 行きかけ順は, 根(接点)→左部分木→右部分木の順で出力を行う.
  • 通りかけ順は左部分木→根(節点)→右部分木の順で出力を行う.
  • 帰りがけ順は, 左部分木→右部分木→根(節点)の順で出力を行う.

コード

#include<iostream>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define NIL -1
#define MAX 30
 
using namespace std;
 
struct Node{
  int parent, left, right;
};
 
Node node[MAX];
 
void preorder(int u){
  if(u == NIL) return;
 
  cout << " " << u;
  preorder(node[u].left);
  preorder(node[u].right);  
}
 
void inorder(int u){
  if(u == NIL) return;
  inorder(node[u].left);
  cout << " " << u;
  inorder(node[u].right);
}
 
void postorder(int u){
  if(u == NIL) return;
  postorder(node[u].left);
  postorder(node[u].right);
  cout << " " << u;
}
 
void init(){
  rep(i, MAX){
    node[i].left = node[i].right = node[i].parent = NIL;
  }
}
 
signed main(){
  int n;
  int id, l, r;
  cin >> n;
  init();
  rep(i, n){
    cin >> id >> l >> r;
    node[id].left = l;
    node[id].right = r;
     
    if(l != NIL) node[l].parent = id;
    if(r != NIL) node[r].parent = id;
  }
   
  int root = 0;
  rep(i, n){
    if(node[i].parent == NIL){
      root = i; 
      break;
    }
  }
  cout << "Preorder" << endl;
  preorder(root);
  cout << "\n";
  cout << "Inorder" << endl;
  inorder(root);
  cout << "\n";
  cout << "Postorder" << endl;
  postorder(root);
  cout << "\n";
 
}
``

【AOJ ALDS1_7】A: Tree - Rooted Trees

問題

Rooted Trees | Aizu Online Judge

方針

  • 根付き木を実装する.
  • Nodeという構造体を定義しておき, ノード番号(id), 親ノード(parent), 子ノード(child), 深さ(depth)というメンバを定義する.
  • 入力にそって親子関係を構築していく.
  • すべて終わったあと, rootノード(parentがNIL)を探す.
  • そのノードをキューに挿入し, 子ノードとその時の深さをqueueにいれ空になるまで繰り返す.

コード

#include <iostream>
#include <queue>
#include <vector>
#include <utility>

#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 NIL -1
#define MAX 100001

using namespace std;

struct Node{
  int id;
  int parent;
  vector<int> child;
  int depth;
  
  void addChild(int c){
    child.pb(c);
  }
    
 void print(){
    cout << "node " << id << ": ";
    cout << "parent = " << parent << ", ";
    cout << "depth = " << depth << ", ";
    cout << (parent == -1?"root":child.size()==0?"leaf":"internal node") << ", ";
    cout << "[";
    if(child.size() != 0){
      rep(i, child.size()-1){
    cout << child[i] << ", ";
      }
      cout << child[child.size()-1];
    }
      cout << "]" << endl;
 }
};

Node node[MAX];

void init(int n){
  rep(i, n){
    node[i].depth = NIL;
    node[i].parent = NIL;
    node[i].child.clear();    
  }
}

signed main(){
  int n;
  int id, k, c, root;
  cin >> n;
  init(n);
  
  root = NIL;

  rep(i, n){
    cin >> id >> k;
    node[id].id = id;
    rep(j, k){
      cin >> c;
      node[id].addChild(c);
      node[c].parent = id;
      node[c].depth = node[id].depth + 1;
    }
  }

  rep(i, n){
    if(node[i].parent == NIL){
      root = i;
      break;
    }
  }
  
  queue<pair<Node, int> > q;
  q.push(make_pair(node[root], -1));
  while(!(q.empty())){
    pair<Node, int> p = q.front(); q.pop();
    node[p.first.id].depth = p.second + 1;
    rep(i, p.first.child.size()){
      q.push(make_pair(node[p.first.child[i]], p.second + 1));
    }
  }
  
  rep(i, n){
    node[i].print();
  }
}