寝癖頭の解法

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

アルゴ式(beta版): C++による「グラフアルゴリズム」幅優先探索 (BFS)

アルゴ式(beta版)の「グラフアルゴリズム幅優先探索 (BFS)からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「グラフアルゴリズム幅優先探索 (BFS)

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

Q1. 頂点を塗る

algo-method.com

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

algo-method.com

/*
アルゴ式(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. 迷路

algo-method.com

/*
アルゴ式(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. デッドロック

algo-method.com

/*
アルゴ式(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