アルゴ式（beta版）の「グラフアルゴリズム」4章:深さ優先探索 (DFS)からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
Q3. 深さ優先探索
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS) Q3. 深さ優先探索 https://algo-method.com/tasks/952 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; void rec(ll v,vector<vector<ll>> &g,vector<ll> &seen){ seen[v]=1; cout<<v<<" "; for(auto v2 : g[v]){ if(seen[v2]){ continue; } rec(v2,g,seen); } } int main(void){ ll n,m; cin>>n>>m; vector<vector<ll>> g(n); for(ll i=0;i<m;i++){ ll a,b; cin>>a>>b; g[a].push_back(b); } for(ll i=0;i<n;i++){ sort(g[i].begin(),g[i].end()); } vector<ll> seen(n,0); rec(0,g,seen); return 0; }
Q4. 辿り着けない頂点
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS) Q4. 辿り着けない頂点 https://algo-method.com/tasks/953 提出コードの解答 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; void rec(ll v,vector<vector<ll>> &g,vector<ll> &seen){ seen[v]=1; for(auto v2 : g[v]){ if(seen[v2]){ continue; } rec(v2,g,seen); } } int main(void){ ll n,m; cin>>n>>m; vector<vector<ll>> g(n); for(ll i=0;i<m;i++){ ll a,b; cin>>a>>b; g[a].push_back(b); } vector<ll> seen(n,0); rec(0,g,seen); ll ans=0; for(ll i=0;i<n;i++){ if(seen[i]==0){ ans++; } } cout<<ans<<endl; return 0; }
Q5. 連結性判定
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS) Q5. 連結性判定 https://algo-method.com/tasks/954 提出コードの解答 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; void rec(ll v,vector<vector<ll>> &g,vector<ll> &seen){ seen[v]=1; for(auto v2 : g[v]){ if(seen[v2]){ continue; } rec(v2,g,seen); } } int main(void){ ll n,m; cin>>n>>m; vector<vector<ll>> g(n); for(ll i=0;i<m;i++){ ll a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } vector<ll> seen(n,0); rec(0,g,seen); for(ll i=0;i<n;i++){ if(seen[i]==0){ cout<<"No"<<endl; return 0; } } cout<<"Yes"<<endl; return 0; }
Q6. 連結成分の個数
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS) Q6. 連結成分の個数 https://algo-method.com/tasks/956 提出コードの解答 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; void DFS(ll v,vector<vector<ll>> &g,vector<ll> &seen){ seen[v]=1; for(auto v2 : g[v]){ if(seen[v2]){ continue; } DFS(v2,g,seen); } } int main(void){ ll n,m; cin>>n>>m; vector<vector<ll>> g(n); for(ll i=0;i<m;i++){ ll a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } vector<ll> seen(n,0); ll ans=0; for(ll i=0;i<n;i++){ if(seen[i]){ continue; } DFS(i,g,seen); ans++; } cout<<ans<<endl; return 0; }
Q7. 塊の個数
/* アルゴ式（beta版）: C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS) Q7. 塊の個数 https://algo-method.com/tasks/955 提出コードの解答 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; bool tf(ll x,ll y,ll h,ll w){ if((0<=x && x<h) &&(0<=y && y<w)){ return true; }else{ return false; } } ll f(ll x,ll y,ll h,ll w){ return (x*w+y); } void DFS(ll v,vector<vector<ll>> &g,vector<ll> &seen){ seen[v]=1; for(auto v2 : g[v]){ if(seen[v2]){ continue; } DFS(v2,g,seen); } } int main(void){ ll h,w; cin>>h>>w; vector<vector<ll>> vv(h,vector<ll>(w,0)); for(ll i=0;i<h;i++){ string s; cin>>s; for(ll j=0;j<w;j++){ if(s[j]=='#'){ vv[i][j]=1; } } } vector<vector<ll>> g(h*w); for(ll i=0;i<h;i++){ for(ll j=0;j<w;j++){ if(vv[i][j]==0){ continue; } ll v=f(i,j,h,w); for(ll k=0;k<4;k++){ ll xx=i+dx[k],yy=j+dy[k]; if(tf(xx,yy,h,w)){ if(vv[xx][yy]==0){ continue; } ll V=f(xx,yy,h,w); g[v].push_back(V); } } } } vector<ll> seen(h*w,0); ll ans=0; for(ll i=0;i<h;i++){ for(ll j=0;j<w;j++){ if(vv[i][j]==0){ continue; } ll v=f(i,j,h,w); if(seen[v]){ continue; } DFS(v,g,seen); ans++; } } cout<<ans<<endl; return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
