寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「グラフアルゴリズム」根付き木の探索

アルゴ式(beta版)の「グラフアルゴリズム」根付き木の探索とはからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「グラフアルゴリズム」根付き木の探索とは

僕が作成、提出したコードは、以下のとおりです。

Q2-1. 箱の中の箱 (1)

algo-method.com

/*
アルゴ式(beta版): C++による「グラフアルゴリズム」根付き木の探索
Q2-1. 箱の中の箱 (1)
https://algo-method.com/tasks/415
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,x;
    cin>>n>>x;
    vector<int> a(n);
    for(int i=1;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    while(x!=0){
        ans++;
        x=a[x];
    }
    cout<<ans<<endl;
    return 0;
}
Q2-3. 行きがけ順

algo-method.com

/*
アルゴ式(beta版): C++による「グラフアルゴリズム」根付き木の探索
Q2-3. 行きがけ順
https://algo-method.com/tasks/525
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
//深さ優先探索 <- Depth First Search
void DFS(int n,vector<vector<int>>& v){
    cout<<n<<" ";
    for(auto i : v[n]){
        DFS(i,v);
    }
}
int main(void){
    int n;
    cin>>n;
    vector<vector<int>> t(n);
    vector<int> p(n);
    for(int i=1;i<n;i++){
        cin>>p[i];
        t[p[i]].push_back(i);
    }
    for(auto& i : t){
        sort(i.begin(),i.end());
    }
    DFS(0,t);
    return 0;
}
Q2-4. 頂点の深さ

algo-method.com

/*
アルゴ式(beta版): C++による「グラフアルゴリズム」根付き木の探索
Q2-4. 頂点の深さ
https://algo-method.com/tasks/529
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void DFS(ll n,vector<vector<ll>>& p,vector<ll>& d){
    for(ll i : p[n]){
        d[i]=d[n]+1;
        DFS(i,p,d);
    }
}
int main(void){
    ll n;
    cin>>n;
    vector<vector<ll>> p(n);
    for(ll i=1;i<n;i++){
        ll pp;
        cin>>pp;
        p[pp].push_back(i);
    }
    vector<ll> d(n);
    d[0]=0;
    DFS(0,p,d);
    for(ll i : d){
        cout<<i<<endl;
    }
    return 0;
}
Q2-5. 木の高さ

algo-method.com

/*
アルゴ式(beta版): C++による「グラフアルゴリズム」根付き木の探索
Q2-5. 木の高さ
https://algo-method.com/tasks/528
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n;
vector<ll> p,v;
void DFS(ll a,ll b){
    v[a]=b;
    for(ll i=1;i<n;i++){
        if(p[i]==a){
            DFS(i,b+1);
        }
    }
}
int main(void){
    cin>>n;
    p.resize(n,0);
    for(ll i=1;i<n;i++){
        ll pp;
        cin>>pp;
        p[i]=pp;
    }
    v.resize(n,0);
    DFS(0,0);
    cout<<*max_element(v.begin(),v.end())<<endl;
    return 0;
}
Q2-6. 子孫の個数

algo-method.com

/*
アルゴ式(beta版): C++による「グラフアルゴリズム」根付き木の探索
Q2-6. 子孫の個数
https://algo-method.com/tasks/434
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll DFS(ll n,vector<vector<ll>>& p,vector<ll>& v){
    for(auto i : p[n]){
        v[n]+=(1+DFS(i,p,v));
    }
    return v[n];
}
int main(void){
    ll n;
    cin>>n;
    vector<vector<ll>> p(n);
    vector<ll> v(n,0);
    for(ll i=1;i<n;i++){
        ll pp;
        cin>>pp;
        p[pp].push_back(i);
    }
    DFS(0,p,v);
    for(auto ans : v){
        cout<<ans<<endl;
    }
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com