寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例

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

C++による「設計技法とデータ構造 (#毎日アルゴ式)」グラフ入門の解答例

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

Q3-1. 友達

algo-method.com

/*
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. フォロー

algo-method.com

/*
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. 友達の友達

algo-method.com

/*
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)

algo-method.com

/*
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. 頂点を塗る

algo-method.com

/*
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)

algo-method.com

/*
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. スモール・ワールド

algo-method.com

/*
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. 迷路

algo-method.com

/*
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. 行きがけ順

algo-method.com

/*
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. 頂点の深さ

algo-method.com

/*
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. 木の高さ

algo-method.com

/*
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. 子孫の個数

algo-method.com

/*
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. デッドロック

algo-method.com

/*
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