topological sort grl_4_b

GRL_4_B トポロジカルソート

GRL_4_B トポロジカルソート
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B

解説

トポロジカルソートとは、有向グラフの矢印が指す順番を守りながらー直線上に頂点を並べることである.
まずどこからも入力がない頂点から開始して、頂点を出力.
頂点をグラフから切り離して辺も削除する.
すると次の入力が無い辺ができるのでその頂点を出力する.
入力が無い頂点が見つからない場合は、一旦すべての未訪問の頂点を調べて入力が無いものから再出発する.

解答

BFSで実装した例.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void tsort(vector<Int> edges[], Int n, vector<Int> &indeg, vector<Int> &result) {
  vector<bool> done(n, false);
  queue<Int> Q;

  Int index = 0;
  loop(i,0,n) {
    if (indeg[i] > 0 || done[i]) continue;
    Q.push(i);
    done[i] = i;
    result[index++] = i;

    while (!Q.empty()) {
      Int u = Q.front(); Q.pop();
      for (Int v: edges[u]) {
        indeg[v]--;
        if (indeg[v] > 0 || done[v]) continue;
        Q.push(v);
        done[v] = true;
        result[index++] = v;
      }
    }
  }
}


int main(void) {
  Int n, e, u, v;
  cin >> n >> e;
  vector<Int> edges[n];
  vector<Int> indeg(n, 0);
  loop(i,0,e) {
    cin >> u >> v;
    edges[u].push_back(v);
    indeg[v]++;
  }

  vector<Int> result(n, 0);
  tsort(edges, n, indeg, result);
  loop(i,0,n) cout << result[i] << ' ';
  cout << endl;
  return 0;
}