Aizu Online Judge in C++ #ALDS1_11_A ~ ALDS1_11_D
僕が作成、提出したコードは、以下のとおりです。
・問題 "Graph"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_A
#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
#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
#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
#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/
