TopCoder SRM 516 Div2 Hard NetworkXMessageRecovery

気づけば後は簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=11239

問題

distinctなアルファベットから構成された文字列がある。
その文字列から生成した部分文字列がN個与えられる。(部分文字列中の文字は元文字列で連続しているとは限らない)

これらの部分文字列から推測できる元文字列のうち、最短でかつ辞書順最小のものを答えよ。

解法

まず、最短という条件から各部分文字列に登場しない文字は元文字列にも登場しない。
次に、distinctという条件より、ある部分文字列に置ける２つの文字の前後関係は、他の部分文字列や元文字列においても維持される。

よって、あとは部分文字列から文字同士の前後関係を求め、トポロジカルソートすればよい。
トポロジカルソートで入力辺がない点を選ぶ際、辞書順最小の文字から処理するだけ。

int valid[256];
int inin[256];

class NetworkXMessageRecovery {
	public:
	string recover(vector <string> messages) {
		int N=messages.size();
		string s;
		int i,x,y;
		ZERO(nod);
		ZERO(inin);
		
		FOR(i,N) FOR(x,messages[i].size()-1) nod[messages[i][x]][messages[i][x+1]]=1;
		FOR(i,N) FOR(x,messages[i].size()) valid[messages[i][x]]=1;
		FOR(x,256) FOR(y,256) inin[y]+=nod[x][y];
		
		while(1) {
			char ok;
			for(ok='A';ok<='z';ok++) if(valid[ok] && inin[ok]==0) break;
			if(ok>'z') break;
			s+=ok;
			valid[ok]=0;
			FOR(x,256) if(nod[ok][x]) inin[x]--;
		}
		return s;
	}
};

まとめ

トポロジカルソートと気づけば簡単。