ハーベル-ハキミの判定法
「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。
入力:負でない整数の列s:d1,d2,・・・,dn(d1≧d2≧・・・≧dn)
出力:sがグラフ的であるならばグラフを出力、そうでないならばNoを出力。
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main(){
//負でない整数列の入力
int N = 0;
cin >> N;
vector<int> d(N,0);
for(int i = 0; i < d.size(); i++){
cin >> d[i];
}
int INF = 0x3fffffff;
bool check = true;
vector< pair<int, vector<int> > > L;
int d_max = 0;
int K = N;
while( (d_max = *max_element(d.begin(),d.end())) >= 1 && check == true){
if( !(K >= d_max+1) ){
check = false;
break;
}
auto itr_i = find(d.begin(), d.end(), d_max);
int i = itr_i - d.begin();
d[i] = -INF;
vector<int> l;
for(int x = i+1; x < d.size(); x++){
int x_max = *max_element(d.begin()+x,d.end());
auto itr_x_i = find(d.begin()+x,d.end(),x_max);
int x_i = itr_x_i - d.begin();
//cout << x_max <<" "<< x_i << endl;
l.emplace_back(x_i);
d[x_i]--;
d_max--;
if(d_max == 0){
break;
}
}
L.emplace_back(make_pair(i,l));
//for(int i =0; i < d.size(); i++){
// cout << d[i] << " ";
//}cout << endl;
for(int j = 0; j < d.size(); j++){
if(d[j] == -1){
check = false;
break;
}
}
if(check == false){
break;
}
K--;
}
if(check == false){
cout << "No" << endl;
}else{
vector< vector<int> > G(N);
vector<int> l;
for(int j = L.size()-1; j >= 0; j--){
int u = L[j].first;
l = L[j].second;
for(int v = 0; v < l.size(); v++){
G[u].emplace_back(l[v]);
G[l[v]].emplace_back(u);
}
}
for(int i = 0; i < G.size(); i++){
cout << i << ":";
for(int j = 0; j < G[i].size(); j++){
cout << G[i][j] << " ";
}cout << endl;
}
}
return 0;
}