寝癖頭の解法

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

アルゴ式(beta版): C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS)

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

C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS)

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

Q3. 深さ優先探索

algo-method.com

/*
アルゴ式(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. 辿り着けない頂点

algo-method.com

/*
アルゴ式(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. 連結性判定

algo-method.com

/*
アルゴ式(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. 連結成分の個数

algo-method.com

/*
アルゴ式(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. 塊の個数

algo-method.com

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