アルゴ式(beta版)の「グラフアルゴリズム」根付き木の探索とはからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。
Q2-1. 箱の中の箱 (1)
/* アルゴ式(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. 行きがけ順
/* アルゴ式(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. 頂点の深さ
/* アルゴ式(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. 木の高さ
/* アルゴ式(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. 子孫の個数
/* アルゴ式(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