データ構造とアルゴリズムテーマセット(中国語)7-6連通セット(25点)問題解をリストする
17178 ワード
私のGIS/CS学習ノート:https://github.com/yunwei37/ZJU-CS-GIS-ClassNotesデータ構造やアルゴリズムに関するメモやptaの問題解もたくさんありますよx
N個の頂点とE個のエッジを持つ無方向図を指定し、DFSとBFSでそれぞれの連通セットをリストします.頂点を0からN−1まで番号付けするとする.探索を行う場合,常に番号が最小の頂点から出発し,番号が増加する順に隣接点にアクセスすると仮定する.
1行目を入力すると2個の整数N(0)が与えられる
「{v 1 v 2...v k}」の形式で、各行に連通セットが出力されます.DFSの結果を出力してからBFSの結果を出力します.
8 6 0 7 0 1 2 0 4 1 2 4 3 5
{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }
N個の頂点とE個のエッジを持つ無方向図を指定し、DFSとBFSでそれぞれの連通セットをリストします.頂点を0からN−1まで番号付けするとする.探索を行う場合,常に番号が最小の頂点から出発し,番号が増加する順に隣接点にアクセスすると仮定する.
入力形式:
1行目を入力すると2個の整数N(0)が与えられる
出力フォーマット:
「{v 1 v 2...v k}」の形式で、各行に連通セットが出力されます.DFSの結果を出力してからBFSの結果を出力します.
サンプルを入力:
8 6 0 7 0 1 2 0 4 1 2 4 3 5
出力サンプル:
{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }
#include
#include
using namespace std;
int edge[10][10]={0};
int v[10];
int visit[10]={0};
//dfs
int dfs(int v1,int n){
int count=1,i;
cout<<v1<<" ";
v[v1]=0;
for(i=0;i<n;++i){
if(edge[v1][i]&&v[i])
count+=dfs(i,n);
}
return count;
}
//bfs
int bfs(int v1,int n){
list<int> a;
int count=1,i,x;
cout<<v1<<" ";
v[v1]=0;
visit[v1]=0;
for(i=0;i<n;++i)
if(edge[v1][i])
a.push_back(i),visit[i]=0;
while(!a.empty()){
x=*a.begin();
a.pop_front();
cout<<x<<" ";
v[x]=0;
++count;
for(i=0;i<n;++i){
if(edge[x][i]&&v[i]&&visit[i])
a.push_back(i),visit[i]=0;
}
}
return count;
}
int main(){
int n,e,n1;
int i,e1,e2;
cin>>n>>e;
for(i=0;i<e;++i){
cin>>e1>>e2;
edge[e1][e2]=1;
edge[e2][e1]=1;
}
//dfs
for(i=0;i<n;i++)
v[i]=1;
n1=n;
cout<<"{ ";
n1=n1-dfs(0,n);
cout<<"}"<<endl;
while(n1>0){
i=0;
while(!v[i])
++i;
cout<<"{ ";
n1-=dfs(i,n);
cout<<"}"<<endl;
}
//bfs
for(i=0;i<n;++i)
visit[i]=1;
for(i=0;i<n;i++)
v[i]=1;
n1=n;
cout<<"{ ";
n1=n1-bfs(0,n);
cout<<"}"<<endl;
while(n1>0){
i=0;
while(!v[i])
++i;
cout<<"{ ";
n1-=bfs(i,n);
cout<<"}"<<endl;
}
return 0;
}