トポロジカルソートを用いた競技プログラミングの問題

Question

現状

トポロジカルソートと呼ばれるアルゴリズムを用いて解くことのできるこの問題(https://beta.atcoder.jp/contests/tenka1-2016-quala/tasks/tenka1_2016_qualA_c)に取り組んでいるのですが行き詰まってしまいました。

発生している問題・エラーメッセージ

次の1つ目のリンクから飛んで頂いてわかるようにいくつかのテストケース(非公開)に正解できていません。また必要でしたらトポロジカルソートの概要は2つ目のリンクからご覧になれます。自分が用いたのはKahn's algorithmと呼ばれるものです。

https://beta.atcoder.jp/contests/tenka1-2016-quala/submissions/2830453

https://ja.m.wikipedia.org/wiki/トポロジカルソート

該当のソースコード

#include <bits/stdc++.h> 

using namespace std;

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

template<class Abel> struct D_Graph {
	int V,E;
	bool **exist;
	vector<vector<pair<int,Abel>>> adj;
	vector<vector<pair<int,Abel>>> adj_inv;
	
	D_Graph(int V_size = 0) : V(V_size)
	{
		init(V);
	}
	
	void init(int V) {
		exist = (bool**)malloc(sizeof(bool*) * (V + 1));
		for(int i = 0; i <= V; ++i){
			exist[i] = (bool*)malloc(sizeof(bool) * (V + 1));
			fill(exist[i],exist[i] + V + 1,0);
		}
		adj.clear(); 
		adj_inv.clear();
		adj.resize(V + 1);
		adj_inv.resize(V + 1);
		for(int i = 1; i <= V; ++i){
			adj[0].push_back({i,0});
			exist[0][i] = 1;
		}
		E = 0;
	}
	
	int deg_out(int v) { return adj[v].size(); }
	
	int deg_in(int v) { return adj_inv[v].size(); }
	
	bool is_leaf(int v) { return deg_out(v) == 0; }
	
	bool is_root(int v) { return deg_in(v) == 0; }
	
	void add_edge(int from, int to, Abel cost = 1) {
		adj[from].push_back({to,cost});
		adj_inv[to].push_back({from,cost});
		exist[from][to] = 1;
		++E;
	}
	
	bool tsort(vector<int> &seq, bool idx_ordered = 0) {
		seq.reserve(V);
		vector<int> in(V + 1);
		stack<int> rt;
		for(int i = 1; i <= V; ++i){
			in[i] = deg_in(i); 
			if(!in[i]){
				rt.push(i);
				seq.push_back(i);
			}
		}
		while(!rt.empty()){
			int r = rt.top();
			rt.pop();
			for(auto e : adj[r]){
				int v = e.first;
				--in[v];
				if(!in[v]){
					rt.push(v);
					if(idx_ordered){
						int pos = 0;
						for(int i = 0; i < seq.size(); ++i) if(seq[i] < v || exist[seq[i]][v]) pos = i + 1;
						seq.insert(begin(seq) + pos,v);
					}else{
						seq.push_back(v);
					}
				}
			}
		}
		if(seq.size() == V) return 1;
		return 0;
	}	
};

int main(){

	D_Graph<int> G(26);
	int N; cin>>N;
	string a,b;
	rep(j,N){
		cin>>a>>b;
		rep(i,min(a.size(),b.size())){
			if(a[i] != b[i]){
				G.add_edge(a[i] - 'a' + 1,b[i] - 'a' + 1);
				break;
			}
			if(i + 1 == b.size()){ cout<<-1<<endl; return 0; }
		}
	}
	vector<int> seq;
	bool j = G.tsort(seq,1);
	if(j){
		for(int c : seq) cout<<(char)(c - 1 + 'a');
	}else{
		cout<<-1;
	}
	cout<<endl;
	
	return 0;
}

補足

D_Graph構造体のメンバ関数tsortが重要な部分になっています。

Answer 1

自己解決しました(下のコードで通すことができました)。
入次数0の頂点を互いを結ぶ辺がないようにまとめて優先度付き降順キューで持ち、
取り出しながらそこまでのソート列にその時点で辞書順を最小化できるように挿入していくことで実現できました。
予め色々なケース(特に自分のコードが対処を困難とするもの)を想定できるようになることも大切ですね。まだまだ精進が必要だと実感しました。

https://beta.atcoder.jp/contests/tenka1-2016-quala/submissions/2858520