【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
方針
- クイックソートはの高速なソートであるが, すべての要素がすでに整列済みの場合など最悪の計算量はである.
- それを解するため, しきい値(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
問題
方針
- 二分木を実装する.
- 行きかけ順(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(); } }