南郵OJ 1048図の幅優先遍歴シーケンス
図の幅優先ループシーケンス
時間制限(通常/Java) :
1000 MS/ 3000 MS 実行メモリ制限:65536 KByte合計コミット:633 テストに合格しました:282
試合の説明
図(graph)はデータ構造 G=(V,E)であり、VはG中のノードの有限非空集合であり、ノードの双対称はエッジ(edge)である.EはG中の辺の有限集合である.V={0,1,2,…,n−1}とし、図中のノードを頂点(vertex)と呼び、有向図(directed graph)は図中のエッジを表すカップリングが秩序的であり、で1本の有向エッジ(弧とも呼ばれる)を表すと、uをそのエッジの始点(尾)、vをエッジの終点(頭)と呼ぶ.無方向図(undirected graph)とは、図中のエッジを表すカップリングが無秩序であり、無方向図中のエッジ(u,v)と(v,u)が同じエッジであることを意味する.
入力エッジは無方向図を構成し,頂点0を起点とする幅優先ループシーケンスを求める.
入力
第1の動作の2つの整数n,eは、図の頂点数と辺数を表す.次のe行は、行ごとに2つの整数で、1つの辺の起点、終点を表し、重複しない、失敗しないことを保証します.1≤n≤20,0≤e≤190
しゅつりょく
前のn行は無方向図の隣接行列を出力し,最後の行は頂点0を起点とする幅優先ループシーケンスを出力し,いずれの起点に対しても終点シーケンス番号が小さい順に各エッジをループする.各シーケンス番号の後にスペースを出力します.
サンプル入力
4 5 0 1 0 3 1 2 1 3 2 3
サンプル出力
0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 3 2
テーマソース
CHENZ
時間制限(通常/Java) :
1000 MS/ 3000 MS 実行メモリ制限:65536 KByte合計コミット:633 テストに合格しました:282
試合の説明
図(graph)はデータ構造 G=(V,E)であり、VはG中のノードの有限非空集合であり、ノードの双対称はエッジ(edge)である.EはG中の辺の有限集合である.V={0,1,2,…,n−1}とし、図中のノードを頂点(vertex)と呼び、有向図(directed graph)は図中のエッジを表すカップリングが秩序的であり、
入力エッジは無方向図を構成し,頂点0を起点とする幅優先ループシーケンスを求める.
入力
第1の動作の2つの整数n,eは、図の頂点数と辺数を表す.次のe行は、行ごとに2つの整数で、1つの辺の起点、終点を表し、重複しない、失敗しないことを保証します.1≤n≤20,0≤e≤190
しゅつりょく
前のn行は無方向図の隣接行列を出力し,最後の行は頂点0を起点とする幅優先ループシーケンスを出力し,いずれの起点に対しても終点シーケンス番号が小さい順に各エッジをループする.各シーケンス番号の後にスペースを出力します.
サンプル入力
4 5 0 1 0 3 1 2 1 3 2 3
サンプル出力
0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 3 2
テーマソース
CHENZ
#include<iostream>
#include<queue>
using namespace std;
int n,e;
bool a[20][20]={0};
bool v[20]={0};
queue<int> q;
int main(){
int i,j;
cin>>n>>e;
while(e--){
cin>>i>>j;
a[i][j]=1;
a[j][i]=1;
}
for(i=0;i<n;++i){
for(j=0;j<n;++j)
cout<<a[i][j]<<" ";
cout<<endl;
}
q.push(0);
v[0]=1;
while(!q.empty()){
i=q.front();
q.pop();
cout<<i<<" ";
for(j=0;j<n;++j){
if(a[i][j] && !v[j]){
q.push(j);
v[j]=1;
}
}
if(q.empty()){ //
for(j=0;j<n;++j){
if(!v[j]){
q.push(j);
v[j]=1; //OL
break;
}
}
}
}
cout<<endl;
}