BEN2のブログ

たまに書いています。

全国統一プログラミング王決定戦予選 D - Restore the Tree

競技プログラミング

全国統一プログラミング王決定戦予選 D - Restore the Tree に関連する、トポロジカルソートについてのメモを残します。

参考

トポロジカルソートとは何か

こちらで詳しく説明されています。実装例も載っています。

トポロジカルソートの実装

この問題を例に、BFS による実装と DFS による実装を載せておく。
まずは DFS から。個人的には DFS の方が分かりやすいです。
未訪問の頂点から DFS して、帰りがけのタイミングで頂点の番号を記録していく。
記録していった頂点番号の列を逆順にするとよい。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<bool> visited;
vector<int> order;

void dfs(int cur) {
  visited.at(cur) = true;
  for (int nx : G.at(cur)) {
    if (visited.at(nx)) continue;
    dfs(nx);
  }
  order.push_back(cur);
}

int main() {
  int V, E; cin >> V >> E;
  G.resize(V);
  visited.resize(V);
  for (int i = 0; i < E; i++) {
    int s, t; cin >> s >> t;
    G.at(s).push_back(t);
  }
  for (int i = 0; i < V; i++) {
    if (visited.at(i)) continue;
    dfs(i);
  }
  reverse(order.begin(), order.end());
  for (int v : order) cout << v << endl;
}

続いて BFS による実装。
各頂点の入次数 (頂点に入ってくる辺数) に注目する。
例えとして頂点を「仕事」とみなす。ある頂点 v の入次数が d であることは、仕事 v に着手する前に終えなければならない仕事が d 個存在することに対応する。
ある頂点 v の入次数が 0 ならば、ただちに仕事 v に着手できることを意味する。
着手した時刻が早い順で仕事 (頂点) を並べるとよい。

実装でやっていること。
BFS していくとき、通過した辺を削除していく (入次数を 1 減らしていく)。
入次数が 0 になったタイミングで、その頂点に訪問する (その仕事に着手する)。
訪問した順に並べるとよい。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<int> indeg;  // 入次数
vector<bool> visited;
vector<int> order;

void bfs(int s) {
  queue<int> q;
  q.push(s);
  visited.at(s) = true;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    order.push_back(cur);
    for (int nx : G.at(cur)) {
      if (visited.at(nx)) continue;
      indeg.at(nx)--;
      if (indeg.at(nx) == 0 && !visited.at(nx)) {
        visited.at(nx) = true;
        q.push(nx);
      }
    }
  }
}

int main() {
  int V, E; cin >> V >> E;
  G.resize(V);
  indeg.resize(V);
  visited.resize(V);
  for (int i = 0; i < E; i++) {
    int s, t; cin >> s >> t;
    G.at(s).push_back(t);
  }
  for (int i = 0; i < V; i++) {
    for (int v : G.at(i)) indeg.at(v)++;
  }
  for (int i = 0; i < V; i++) {
    if (indeg.at(i) == 0 && !visited.at(i)) bfs(i);
  }
  for (int v : order) cout << v << endl;
}

Restore the Tree

入力例 2 について、元の根付き木 ( N 頂点と N-1 本の黒色の有向辺) と書き加えられた有向辺 (緑色) を図にしてみた。
赤い数字は、トポロジカルソートしたときの index を表している。
この問題では、入次数が 0 の頂点は根であることが確定する。

f:id:BEN2suzuka:20200627202459p:plain

ある頂点 v へ伸びている有向辺が複数ある場合、それらの辺のうち、赤い数字の最も大きい頂点 u から伸びている有向辺が元の根付き木を構成する辺であり、元の根付き木において u が v の親である。

実装では BFS でトポロジカルソートする。
入次数が 0 になった頂点 v へ訪問するとき、どの頂点から来たかを記録する (これが親)。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<int> indeg;  // 入次数
vector<bool> visited;
vector<int> ans;

void bfs(int s) {
  queue<int> q;
  q.push(s);
  visited.at(s) = true;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int nx : G.at(cur)) {
      if (visited.at(nx)) continue;
      indeg.at(nx)--;
      if (indeg.at(nx) == 0 && !visited.at(nx)) {
        visited.at(nx) = true;
        ans.at(nx) = cur + 1;  // nx の親は cur + 1
        q.push(nx);
      }
    }
  }
}

int main() {
  int N, M; cin >> N >> M;
  G.resize(N);
  indeg.resize(N);
  visited.resize(N);
  ans.resize(N);
  for (int i = 0; i < N-1+M; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    G.at(a).push_back(b);
  }
  for (int i = 0; i < N; i++) {
    for (int e : G.at(i)) indeg.at(e)++;
  }
  for (int i = 0; i < N; i++) {
    if (indeg.at(i) == 0 && !visited.at(i)) bfs(i);
  }
  for (int v : ans) cout << v << endl;
}