寝癖頭の解法

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

Aizu Online Judge in C++ #ALDS1_11_A ~ ALDS1_11_D

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

Aizu Online Judge in C++ #ALDS1_11_A ~ ALDS1_11_D

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

・問題 "Graph"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_A

/*
Aizu Online Judge in C++ #ALDS1_11_A : Graph
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_A
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    cin>>n;
    vector<vector<ll>> g(n,vector<ll>(n,0));
    for(ll i=0;i<n;i++){
        int u,k;
        cin>>u>>k;
        for(ll j=0;j<k;j++){
            ll v;
            cin>>v;
            g[u-1][v-1]=1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<g[i][j]<<((j==n-1) ? "\n" : " ");
        }
    }
    return 0;
}

・問題 "Depth First Search"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_B

/*
Aizu Online Judge in C++ #ALDS1_11_B : Depth First Search
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_B
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n;
bool tf[10005];
ll d[10005],f[10005];
vector<ll> g[10005];
ll num=0;
void DFS(ll i){
    tf[i]=true;
    num++;
    d[i]=num;
    for(ll j=0;j<g[i].size();j++){
        if(tf[g[i][j]]==false){
            DFS(g[i][j]);
        }
    }
    num++;
    f[i]=num;
}
void F(void){
    for(ll i=1;i<=n;i++){
        if(tf[i]==false){
            DFS(i);
        }
    }
    for(ll i=1;i<=n;i++){
        cout<<i<<" ";
        cout<<d[i]<<" ";
        cout<<f[i]<<endl;
    }
}
int main(void){
    cin>>n;
    ll u,k,v;
    for(ll i=1;i<=n;i++){
        cin>>u>>k;
        for(ll j=0;j<k;j++){
            cin>>v;
            g[u].push_back(v);
        }
    }
    F();
    return 0; 
}

・問題 "Breadth First Search"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_C

/*
Aizu Online Judge in C++ #ALDS1_11_C : Breadth First Search
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_C
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n;
ll g[101][101],d[101];
void BFS(void){
    bool tf[101];
    memset(d,-1,sizeof(d));
    memset(tf,false,sizeof(tf));
    d[0]=0;
    tf[0]=true;
    queue<ll> q;
    q.push(0);
    while(!(q.empty())){
        ll v=q.front();
        q.pop();
        for(ll i=0;i<n;i++){
            if(tf[i]==false && g[v][i]==1){
                tf[i]=true;
                d[i]=d[v]+1;
                q.push(i);
            }
        }
    }
}
int main(void){
    cin>>n;
    for(ll i=0;i<n;i++){
        ll u,k,v;
        cin>>u>>k;
        for(ll j=0;j<k;j++){
            cin>>v;
            g[u-1][v-1]=1;
        }
    }
    BFS();
    for(ll i=0;i<n;i++){
        cout<<i+1<<" "<<d[i]<<endl;
    }
    return 0;
}

・問題 "Connected Components"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_D

/*
Aizu Online Judge in C++ #ALDS1_11_D : Connected Components
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_D
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m;
vector<ll> v[100001];
ll s,t,id[100001];
bool tf[100001]={false};
void f(ll x,ll u){
    tf[x]=true;
    id[x]=u;
    ll num;
    for(ll i=0;i<v[x].size();i++){
        num=v[x][i];
        if(tf[num]==false){
            f(num,u);
        }
    }
}
int main(void){
    cin>>n>>m;
    ll a,b;
    for(ll i=0;i<m;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(ll i=0;i<n;i++){
        if(tf[i]==false){
            f(i,i);
        }
    }
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        cin>>s>>t;
        if(id[s]==id[t]){
            cout<<"yes"<<endl;
        }else{
            cout<<"no"<<endl;
        }
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/