yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

ハーベル-ハキミの判定法

「やさしいグラフ論」を読んでプログラムしたくなったので、載せておきます。

ソースコードC++です。

 

入力:負でない整数の列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;
}