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/