アルゴ式（beta版）の「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例
僕が作成、提出したコードは、以下のとおりです。
Q3-1. 友達
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-1. 友達 https://algo-method.com/tasks/411 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,a,b; cin>>n>>a>>b; vector<string> s(n); for(int i=0;i<n;i++){ cin>>s[i]; } if(s[a].at(b)=='o'){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }
・Q3-2. フォロー
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-2. フォロー https://algo-method.com/tasks/412 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<vector<int>> turtle(n); vector<int> a(m),b(m); for(int i=0;i<m;i++){ cin>>a[i]>>b[i]; turtle[a[i]].push_back(b[i]); } for(int i=0;i<n;i++){ sort(turtle[i].begin(),turtle[i].end()); for(auto j : turtle[i]){ cout<<j<<" "; } cout<<endl; } return 0; }
・Q3-3. 友達の友達
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-3. 友達の友達 https://algo-method.com/tasks/413 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m,x; cin>>n>>m>>x; vector<vector<int>> v(n); vector<int> a(m),b(m); for(int i=0;i<m;i++){ cin>>a[i]>>b[i]; v[a[i]].push_back(b[i]); v[b[i]].push_back(a[i]); } set<int> aruruF; for(auto num : v[x]){ aruruF.insert(num); } set<int> aruruFF; for(auto n1 : v[x]){ for(auto n2 : v[n1]){ if(n2!=x && aruruF.count(n2)!=1){ aruruFF.insert(n2); } } } cout<<aruruFF.size()<<endl; return 0; }
・Q3-4. 箱の中の箱 (1)
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-4. 箱の中の箱 (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; }
・Q3-5. 頂点を塗る
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-5. 頂点を塗る https://algo-method.com/tasks/414 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<vector<int>> v(n); vector<int> a(m),b(m); for(int i=0;i<m;i++){ cin>>a[i]>>b[i]; v[a[i]].push_back(b[i]); v[b[i]].push_back(a[i]); } for(int i=0;i<n;i++){ sort(v[i].begin(),v[i].end()); } cout<<0<<endl; vector<int> vi(n,100000000); vi[0]=0; vector<vector<int>> vv(n+1); vv[0].push_back(0); for(int i=0;i<n;i++){ vector<int> ans; for(auto j : vv[i]){ for(auto k : v[j]){ if(vi[k]!=100000000){ continue; } vi[k]=vi[j]+1; vv[i+1].push_back(k); ans.push_back(k); } } sort(ans.begin(),ans.end()); for(auto out : ans){ cout<<out<<" "; } cout<<endl; } return 0; }
・Q3-6. 箱の中の箱 (2)
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-6. 箱の中の箱 (2) https://algo-method.com/tasks/416 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> a(n); for(int i=1;i<n;i++){ cin>>a[i]; } for(int i=1;i<n;i++){ int j=i; int ans=0; while(j!=0){ ans++; j=a[j]; } cout<<ans<<endl; } return 0; }
・Q3-7. スモール・ワールド
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-7. スモール・ワールド https://algo-method.com/tasks/418 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<vector<int>> v(n); vector<int> a(m),b(m); for(int i=0;i<m;i++){ cin>>a[i]>>b[i]; v[a[i]].push_back(b[i]); v[b[i]].push_back(a[i]); } queue<int> q; q.push(0); vector<int> vi(n,-1); vi[0]=0; while(!(q.empty())){ int i=q.front(); q.pop(); for(int j : v[i]){ if(vi[j]==-1){ vi[j]=vi[i]+1; q.push(j); } } } int ans=-1; for(auto i : vi){ ans=max(ans,i); } cout<<ans<<endl; return 0; }
・Q3-8. 迷路
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-8. 迷路 https://algo-method.com/tasks/424 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int h,w; cin>>h>>w; int x0,y0,x1,y1; cin>>x0>>y0>>x1>>y1; vector<string> s(h); for(int i=0;i<h;i++){ cin>>s[i]; } queue<pair<int,int>> q; q.push(make_pair(x0,y0)); vector<vector<int>> vv(h,vector<int>(w,-1)); vv[x0][y0]=0; vector<int> v1={1,0,-1,0}; vector<int> v2={0,1,0,-1}; while(!(q.empty())){ pair<int,int> p=q.front(); q.pop(); for(int i=0;i<4;i++){ int Iv1=p.first+v1[i]; int Iv2=p.second+v2[i]; if((0<=Iv1 && Iv1<h) && (0<=Iv2 && Iv2<w)){ if(s[Iv1].at(Iv2)=='W' && vv[Iv1][Iv2]==-1){ vv[Iv1][Iv2]=vv[p.first][p.second]+1; q.push(make_pair(Iv1,Iv2)); } } } } cout<<vv[x1][y1]<<endl; return 0; }
・Q3-9. 行きがけ順
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-9. 行きがけ順 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; }
・Q3-10. 頂点の深さ
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-10. 頂点の深さ 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; }
・Q3-11. 木の高さ
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-11. 木の高さ 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; }
・Q3-12. 子孫の個数
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-12. 子孫の個数 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; }
・Q3-13. デッドロック
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例 Q3-13. デッドロック https://algo-method.com/tasks/536 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,m; cin>>n>>m; vector<ll> f(m),s(m); vector<vector<ll>> graph(n); vector<ll> v(n,0); for(ll i=0;i<m;i++){ cin>>f[i]>>s[i]; graph[f[i]].push_back(s[i]); v[s[i]]++; } queue<ll> q; for(ll i=0;i<n;i++){ if(v[i]==0){ q.push(i); } } while(!(q.empty())){ ll i=q.front(); q.pop(); for(auto j : graph[i]){ v[j]--; if(v[j]==0){ q.push(j); } } } cout<<((accumulate(v.begin(),v.end(),0)==0) ? "Yes" : "No")<<endl; return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
