CODE THANKS FESTIVAL 2014 B : H - しりとりゲーム

本番グラフかと思ってずっと悩んでた。
http://code-thanks-festival-2014-b-open.contest.atcoder.jp/tasks/code_thanks_festival_14_qualb_h

問題

N個の英単語が与えられるので、これを用いてしりとりを行う。
１回のプレイで全単語を１回ずつ使いたい。
ただし以下のルールがある。

• 各単語をそのまま使う代わりに、反転した単語を使っても良い。
• 任意の単語を追加しても良い。

必要な単語の最小追加数を答えよ。

解法

アルファベットを点としたグラフを考える。
各単語について、先頭文字と末尾の文字に相当する点を無向辺でつなぐ。

ここで幾つか辺を追加して、全部の辺を１回ずつつなぐ順路を作ることを考える。
そのためには、全頂点が連結でかつ次数が奇数の点が２個以下であることである。

以下のようにすれば追加する辺の数を最小化できる。

• まずUnion-Findで頂点の連結関係を求める。
• 各連結頂点において、次数が奇数の点の数を求める。奇数の点の数を最小化するには、奇数の点同士を結ぶ辺がいるので(次数が奇数の点の数)/2だけ辺が要る。また、他の連結成分と連結するために、最小でも1つの辺が要る。

上記計算で求めた追加辺から(最初の単語を任意に選べることから)1引いた値が答え。

class UF {
	public:
	static const int ufmax=100052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[find(x)];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N;
int num[26],odd[26];
UF uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		x=s[0]-'a',y=s[s.size()-1]-'a';
		num[x]++;
		num[y]++;
		uf.unite(x,y);
	}
	
	FOR(i,26) if(num[i]%2) odd[uf[i]]++;
	FOR(i,26) odd[i]/=2;
	FOR(i,26) if(uf[i]==i && num[i]) odd[uf[i]]=max(1,odd[uf[i]]);
	cout<<accumulate(odd,odd+26,0)-1<<endl;
}

まとめ

次数の問題に落とし込むことは思いつかなかったな…。