ALDS 1_7_A의 C++ 코드를 해석하고 Rust로 다시 구현
ALDS 1_7_A
근부목의 표현
따라서 리프트의 깊이는 자신보다 1이 많고 라이트의 깊이는 같다.
C++ 코드
프로그래밍 경기의 알고리즘과 데이터 구조를 공략하기 위해에 주석이 적당히 첨가되었다.
#include<iostream>
using namespace std;
#define MAX 100005
#define NIL -1
struct Node {int p, l, r ;};
// pは自分の親のノード
// lは自分から見て最も左の子のノード
// rは自分の右隣のノード
Node T[MAX];
int n, D[MAX];
void print(int u) {
int i, c;
cout << "node " << u << ": ";
cout << "parent = " << T[u].p << ", ";
cout << "depth = " << D[u] << ", ";
if (T[u].p == NIL) cout << "root, " ;
else if (T[u].l == NIL) cout << "leaf, ";
else cout << "internal node, ";
cout << "[";
for (i = 0, c= T[u].l; c != NIL; i++, c=T[c].r){
if (i) cout << ", ";
cout << c;
}
cout << "]" << endl ;
}
void rec (int u, int p){
// u : ノード番号
// p : 深さ
// recはD[u]を変更する。
D[u] = p; //u番目のノードの深さにpを設定
// 右のノード => 同じ深さを設定
if (T[u].r != NIL) rec(T[u].r, p);
// T[u]が最も左のノードだった場合、次の段(p+1)に移動。
if (T[u].l != NIL) rec(T[u].l, p+1);
}
int main(){
int i,j,d,v,c,l,r;
cin >> n;
// T[]の初期化
for (i=0; i<n;i++) T[i].p = T[i].l = T[i].r = NIL;
for (i=0; i<n; i++){
// vはid、dは子の数に対応
cin >> v >> d;
// id: vのノードは、d個の子ノードをもつ。
for (j=0; j<d; j++){
cin >> c;
if (j==0) T[v].l = c; // 最初の子供をv番目の左側の子供として設定。
else T[l].r = c; // l番目のノードの右隣ノードとしてノードcを設定
l = c; // lにノードcを設定。次のノードの右隣ノードを決定するために使う。
T[c].p = v; // c番目の親にid: vのノードを設定。
}
}
for (i=0; i < n; i++){
if (T[i].p==NIL) r=i; // 親がいないノードを探してrとしている。
}
// 親番号から探索開始
rec(r,0);
for (i=0; i<n; i++) print(i);
return 0;
}
Rust에서 재설치
i32와usize가 섞인 as는 더럽고 for문의parameter 정의는 더럽기 때문에 기분이 좋으면 다시 씁니다.
use std::io;
fn read<T: std::str::FromStr>() -> Vec<T> {
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
buf.trim().split(' ').flat_map(str::parse).collect()
}
#[derive(Debug, Clone)]
struct Node {
parent: i32,
left: i32,
right: i32
}
impl Node {
fn set_left(&mut self, left: i32) {
self.left = left
}
fn set_right(&mut self, right: i32) {
self.right = right
}
}
fn printer(id :usize, tree: &Vec<Node>, depth: &Vec<i32>){
let node_type = if tree[id].parent == -1 {
"root"
} else if tree[id].left == -1 {
"leaf"
} else {
"internal node"
};
print!("node {node}: parent = {parent}, depth = {depth}, {node_type}, [",
node = id,
parent = tree[id].parent,
depth = depth[id],
node_type = node_type);
let mut i = 0;
let mut c = tree[id].left;
while c != -1 { // leftがいるとき
if i > 0 {print!(", ")};
print!("{}", c);
i += 1;
c=tree[c as usize].right;
}
println!("]")
}
fn calc_depth(tree: &Vec<Node>, depth: &mut Vec<i32>, id: usize, d: usize){
depth[id] = d as i32;
if tree[id].right != -1 {calc_depth(&tree, depth, tree[id].right as usize, d)}
if tree[id].left != -1 {calc_depth(&tree, depth, tree[id].left as usize, d+1)}
}
fn main() {
let node_num = read::<usize>()[0];
// T[]に対応
let mut tree = vec![Node{parent: -1,left: -1, right: -1}; node_num];
// D[]に対応
let mut depth = vec![0; node_num];
for _i in 0..node_num {
let mut line = read::<usize>();
let id = line.remove(0);
let _child_num = line.remove(0) as usize;
let childs = line;
let mut counter = 0;
let mut left = 0;
for c in childs {
if counter == 0 {
tree[id].set_left(c as i32);
} else {
tree[left].set_right(c as i32);
}
left = c as usize;
tree[c].parent = id as i32;
counter += 1
}
}
let mut root = 0;
for i in 0..node_num {
if tree[i].parent == -1 {
root = i;
}
}
calc_depth(&tree , &mut depth, root, 0);
for i in 0..node_num {printer(i, &tree, &depth)}
}
Reference
이 문제에 관하여(ALDS 1_7_A의 C++ 코드를 해석하고 Rust로 다시 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/tomkei/articles/a13573f83c18a1텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)