アルゴ式（beta版）の「グラフアルゴリズム」幅優先探索 (BFS)からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
Q1. 頂点を塗る
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」幅優先探索 (BFS) Q1. 頂点を塗る 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; }
Q2. スモール・ワールド
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」幅優先探索 (BFS) Q2. スモール・ワールド 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. 迷路
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」幅優先探索 (BFS) Q3. 迷路 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; }
Ex. デッドロック
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」幅優先探索 (BFS) Ex. デッドロック 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
