Topological Sort

コードについての説明

有向グラフ $G = (V, E)$ が DAG(有向閉路を持たないグラフ) であるかの判定および DAG の場合は頂点をトポロジカル順序にソートするアルゴリズム.
頂点集合 $V$ から始めて, 現在残っている頂点集合 $S$ から辺が入ってこないような頂点 $v$ を選び, $S = S \setminus \{ v \}$ として空集合となるまで続ける. 途中で頂点 $v$ が存在しなくなったらグラフが DAG でないと判定する. $S$ から辺が入ってこないような頂点は残りの頂点集合から入ってくる辺の次数が $0$ である頂点をキューで管理することで効率よく取ってくることが可能.
正当性は残りの頂点の中で上のように選んだ頂点 $v$ を先頭においてもトポロジカル順序に反さないこと, そして元のグラフが DAG である場合そのような頂点は残りの頂点集合が空集合でない限り常に存在することから言える.

(関数)
solve(): DAG かどうか(true / false) を返し, true なら $res$ にトポロジカル順序にソートされた頂点列が格納される.

時間計算量: $\O (n + m)$

コード

class tsort {
public:
	int V;
	vector<vector<int> > G;
	vector<int> deg,res;
	tsort(int node_size) : V(node_size), G(V), deg(V, 0){}
	void add_edge(int from,int to){
		G[from].push_back(to);
		deg[to]++;
	}
	bool solve() {
		queue<int> que;
		for(int i = 0; i < V; i++){
			if(deg[i] == 0){
				que.push(i);
			}
		}
		while(!que.empty()){
			int p = que.front();
			que.pop();
			res.push_back(p);
			for(int v : G[p]){
				if(--deg[v] == 0){
					que.push(v);
				}
			}
		}
		return (*max_element(deg.begin(),deg.end()) == 0);
	}
};

verify 用の問題

AOJ : Neko's Treasure 提出コード