トポロジカルソート

トポロジカルソートの勉強をした。

もともとの目的は EDPC ( Educatiocal DP contest ) の G. Longest Path を解くためにやった。

これ
G - Longest Path。

トポロジカルソートとは

いい感じに有向グラフの頂点の番号付けを変える操作。
いい感じっていうのは、前から後ろに自然に流れているみたいな。
wikipedia を見てほしい。これ
トポロジカルソート - Wikipedia。

実装する

参考になったのは、
上に書いた wikipedia と、
トポロジカルソート - Thoth Children。
Kahn の方法ってやつで書いたつもり。

有向非巡回グラフの場合にやる。
一言で言うと、
入力辺の無い頂点と、それに付随する辺を除く、ことを繰り返す
ということ。

S を deque とします。
python なら list で十分です。
C++ なら　deque 使わないとやりにくい気がする。
S には入力辺が無い頂点を格納する。

T を空リストとする。
最終的にこれがトポロジカルソートの結果を格納する。

1. V を というリストを作る。

2. 入力辺の無い頂点を S に格納する。

3. 次の操作 4--6 を繰り返す。

4. S の前方から 頂点 s を一つ取り出し、T の後方に格納する。

5. 次の操作 6 を繰り返す。

6. s から出ている辺を除く。これに伴い、V の値が更新される。これが 0 になった頂点を新たに、S に追加する。

実装 ( python )

AOJ のトポロジカルソートへの解答の形で書いてある。
これ
トポロジカルソート | グラフ | Aizu Online Judge。

def topologicalsort(N,E):
    V = [0]*N
    for i in range(N):
        for y in E[i]:
            V[y] += 1
    S = [ i for i in range(N) if V[i] == 0]
    SORTED = []
    while S:
        s = S.pop(0)
        SORTED.append(s)
        for t in E[s]:
            V[t] -= 1
            if V[t] == 0:
                S.append(t)
    return SORTED
    
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( int, input().split())
    # x, y = x-1, y-1
    E[x].append(y)
ANS = topologicalsort(N, E)
for i in range(N):
    print(ANS[i])

EDPC G

python

これ python は通るけど、pypy は TLE する。
ナンデ？？？

def topologicalsort(N,E):
    V = [0]*N
    for i in range(N):
        for y in E[i]:
            V[y] += 1
    S = [ i for i in range(N) if V[i] == 0]
    SORTED = []
    while S:
        s = S.pop(0)
        SORTED.append(s)
        for t in E[s]:
            V[t] -= 1
            if V[t] == 0:
                S.append(t)
    return SORTED
    
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    E[x].append(y)
V = topologicalsort(N, E)
ANS = [0]*N
for i in range(N):
    v = V[i]
    t = ANS[v]+1
    for e in E[v]:
        if t > ANS[e]:
            ANS[e] = t
print( max(ANS)) 

C++

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <climits>
#include <deque>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(),x.end()

int main()
{
  int N, M, x, y, s, l;
  cin >> N >> M;
  int V[N];
  vector<int> E[N], T;
  deque<int> S;
  for (int i = 0; i < N; ++i) {
    V[i] = 0;
  }
  for (int i = 0; i < M; ++i) {
    cin >> x >> y;
    x--; y--;
    E[x].push_back(y);
    V[y] += 1;
  }
  for (int i = 0; i < N; ++i) {
    if (V[i] == 0) {
      S.push_back(i);
    }
  }

  while (S.size()) {
    s = S[0];
    S.pop_front();
    T.push_back(s);
    l = E[s].size();
    for (int i = 0; i < l; ++i) {
      V[E[s][i]]--;
      if (V[E[s][i]] == 0) {
        S.push_back(E[s][i]);
      }
    }
  }
  int ANS[N];
  for (int i = 0; i < N; ++i) {
    ANS[i] = 0;
  }
  int v, t;
  for (int i = 0; i < N; ++i) {
    v = T[i];
    t = ANS[v] + 1;
    l = E[v].size();
    for (int j = 0; j < l; ++j) {
      if (t > ANS[E[v][j]]) {
        ANS[E[v][j]] = t;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    if (ans < ANS[i]) {
      ans = ANS[i];
    }
  }
  cout << ans << "\n";
  return 0;
}