土下座しながら探索中

主に競技プログラミング

Codeforces AIM Tech Round (Div. 2) C : Graph and String

問題リンク :
http://codeforces.com/contest/624/problem/C

問題概要 :
長さnの{'a','b','c'}で構成されている文字列が存在した
これを次の手順でグラフに変換した
1. n個のノードを作成、各ノードに1から順に番号を割り振る
2. 異なる2つのノード番号i,jについて、文字列のi番とj番が一致または隣接していればノードiとノードjに辺を張る
ここで、隣接とはa-b,b-cのことをであり、a-cは隣接とは言わない
この手順でグラフを作成したあと、文字列を消した

グラフが与えられるので、上記の手順にしたがった場合与えられたグラフになるような文字列を出力せよ
複数存在するならどれか1つでよい
存在しない場合はNoと出力せよ

解法:
ノードがちょうど1つしか存在しない場合、明らかに答えとなる文字列は存在する
'a'か'b'か'c'である
どれか好きなのを出力すると良い

ノードがちょうど2つ存在する場合、これも必ず答えとなる文字列は存在する
その2つのノード間に辺があるなら、'a'-'b'か'b'-'c'か'a'-'a','b'-'b','c'-'c'のいずれかを出力するとよい
辺がないなら隣接していないので'a'-'c'が答えとなる

ノードが3つ以上存在する場合、次のような部分をグラフから探す
f:id:tei3344:20160205044801p:plain
このような部分が存在しないなら、存在する頂点は全て完全グラフの一部となっているはずである
つまり完全グラフが何個か存在することになる
完全グラフが1つしかないなら、明らかに答えは存在する(全て同じ文字とか)
完全グラフが2つなら、0の完全グラフと2の完全グラフが存在する
それ以上存在するなら答えはない 0と2で2つまでなら完全グラフをつくれるが、もう1つ追加しからそれが0の完全グラフであれ、1であれ、2であれ、どれでも最初の2つの完全グラフとくっついてしまう

上の図のような、三角形の一辺を抜いた部分が存在するなら、
その図にある0番のノードは'b'であり、1番のノードと2番のノードはどちらかが'a'でもう片方が'c'である
このとき、1番のノードに辺がつながっているノードは1に割り当てられた英小文字('a'か'c')か0に割り当てられた英小文字('b')と一致するはずである
同様に2番のノードに辺がつながっているノードは2番に割り当てられた英小文字('a'か'c')か0番に割り当てられた英小文字('b')と一致するはず
f:id:tei3344:20160205050548p:plain
これらを集合にしたとき(上の図でいう、点線内のノード番号を集合としたとき)
両方の集合に属することができるのは'b'しかないので、それらのノードには'b'を割り当てる
そうでないものは、どちらかを'a'の集合、もう片方は'c'の集合と決めて(どっちでも良いので)割り当てる
あとは頂点集合全体を見て、'a','b','c'のいずれも割り当てられていないものがあればNoと出力し、
そうでないなら答えとなる文字列を生成して、一応入力のグラフができるかチェックして大丈夫ならそれを出力する

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX = 600;

const string YES = "Yes";
const string NO = "No";
typedef pair<int,int> ii;

int V,E;
vector<int> G[MAX];
bool mat[MAX][MAX];
bool vmat[MAX][MAX];
vector<ii> edges;
char c[MAX];

void dfs(int cur,set<int> &S) {
  rep(i,(int)G[cur].size()) {
    int next = G[cur][i];
    if( S.count(next) ) continue;
    S.insert(next);
    dfs(next,S);
  }
}

int compute() {

  if( V == 1 ) {
    cout << YES << endl;
    return puts("b");
  }
  if( (int)((V*(V-1))/2) == E ) {
    cout << YES << endl;
    return puts(string(V,'b').c_str());
  }

  rep(i,V) c[i] = '$';
  set<int> S0;
  set<int> S2;
  rep(i,(int)edges.size()) {
    int s = edges[i].first;
    int t = edges[i].second;
    rep(p,V) {
      if( s == p || t == p ) continue;
      if( !mat[p][t] && !mat[p][s] ) continue;
      if( mat[p][t] && mat[p][s] ) continue;
      int ID0,ID1 , ID2;
      if( mat[p][s] ) {
	ID0 = t, ID1 = s, ID2 = p;
      } else {
	ID0 = s, ID1 = t, ID2 = p;
      }

      S0.insert(ID1);
      S0.insert(ID0);
      S2.insert(ID1);
      S2.insert(ID2);
      rep(k,V) {
	if( k == s || k == t || k == p ) continue;
	if( mat[ID0][k] ) S0.insert(k);
	if( mat[ID2][k] ) S2.insert(k);
      }
      goto Skip;
    }
  }
 Skip:;

  if( S0.empty() ) {
    S0.insert(0);
    dfs(0,S0);
    rep(i,V) if( !S0.count(i) ) {
      S2.insert(i);
      dfs(i,S2);
      break;
    }
    for(set<int>::iterator it=S0.begin();it!=S0.end();it++) {
      c[*it] = 'a';
    }

    for(set<int>::iterator it=S2.begin();it!=S2.end();it++) {
      c[*it] = 'c';
    }
    rep(i,V) if( c[i] == '$' ) {
      return puts(NO.c_str());
    }
    puts(YES.c_str());
    rep(i,V) {
      printf("%c",c[i]);
    } puts("");
    return 0;
  }

  rep(i,V) {
    if( S0.count(i) && S2.count(i) ) {
      c[i] = 'b';
    } else if( S0.count(i) ) {
      c[i] = 'a';
    } else if( S2.count(i) ) {
      c[i] = 'c';
    }
  }
  /*
  cout << "S0::" << endl;
  for(set<int>::iterator it=S0.begin();it!=S0.end();it++) {
    cout << *it << " ";
  } puts("");

  cout << "S2::" << endl;
  for(set<int>::iterator it=S2.begin();it!=S2.end();it++) {
    cout << *it << " ";
  } puts("");
  */
  string answer = "";
  rep(i,V) {
    if( c[i] == '$' ) {
      return puts(NO.c_str());
    }
    answer += string(1,c[i]);
  }

  
  rep(i,V) REP(j,i+1,V) {
    int v1 = c[i] - 'a';
    int v2 = c[j] - 'a';
    if( abs(v1-v2) <= 1 ) {
      vmat[i][j] = vmat[j][i] = true;
    }
  }

  rep(i,V) rep(j,V) if( mat[i][j] != vmat[i][j] ) {
    return puts(NO.c_str());
  }
  puts(YES.c_str());
  return puts(answer.c_str());
}

int main(){
  scanf("%d %d",&V,&E);
  int s,t;
  rep(i,E) {
    scanf(" %d %d",&s,&t);
    --s, --t;
    mat[s][t] = mat[t][s] = true;
    G[s].push_back(t);
    G[t].push_back(s);
    if( s > t ) swap(s,t);
    edges.push_back(ii(s,t));
  }
  compute();
  return 0;
}