深さ優先探索

問題

実行時間制限: 1 sec / メモリ制限: 65536 KB
有向グラフ \(G = (V,E)\) の各頂点に以下のタイムスタンプを押す。

  • タイムスタンプ \(d[v]\) : \(v\) を最初に訪問した発見時刻を記録する。
  • タイムスタンプ \(f[v]\) : \(v\) の隣接リストを調べ終わった完了時刻を記録する。

以下の仕様に基づき、与えられた有向グラフ \(G = (V,E)\) に対する深さ優先探索の動作を示すプログラムを作成せよ。

  • \(G\) は隣接リスト表現の形式で与えらえる。各頂点には \(1\) から \(n\) までの番号が付されている。
  • 各隣接リストの頂点は番号が小さい順に並べられている。
  • プログラムは各頂点の発見時刻と完了時刻を報告する。
  • 深さ優先探索の過程において、訪問する頂点の候補が複数ある場合は頂点番号が小さいものから選択する。
  • 最初に訪問する頂点の開始時刻は \(1\) とする。

制約

  • \(1 \leqq n \leqq 100\)

入力

最初の行に \(G\) の頂点数 \(n\) が与えらえる。続く \(n\) 行で各頂点 \(u\) の隣接リスト \(Adj[u]\) が以下の形式で与えられる。

\(u \hspace{8px} k \hspace{8px} v_1 \hspace{8px} v_2 \hspace{8px} ... \hspace{8px} v_k\)

\(u\) は頂点の番号、\(k\) は \(u\) の出次数、 \(v_1 v_2 ... v_k\) は \(u\) に隣接する頂点の番号を示す。

出力

各頂点について \(id\)、\(d\)、\(f\) を空白区切りで \(1\) 行にして、頂点の番号順で出力せよ。 \(id\) は頂点の番号、 \(d\) はその頂点の発見時刻、 \(f\) はその頂点の完了時刻とする。

例1

入力

\(6\)
\(1 \hspace{8px} 2 \hspace{8px} 2 \hspace{8px} 3\)
\(2 \hspace{8px} 2 \hspace{8px} 3 \hspace{8px} 4\)
\(3 \hspace{8px} 1 \hspace{8px} 5\)
\(4 \hspace{8px} 1 \hspace{8px} 6\)
\(5 \hspace{8px} 1 \hspace{8px} 6\)
\(6 \hspace{8px} 0\)

出力

\(1 \hspace{8px} 1 \hspace{8px} 12\)
\(2 \hspace{8px} 2 \hspace{8px} 11\)
\(3 \hspace{8px} 3 \hspace{8px} 8\)
\(4 \hspace{8px} 9 \hspace{8px} 10\)
\(5 \hspace{8px} 4 \hspace{8px} 7\)
\(6 \hspace{8px} 5 \hspace{8px} 6\)

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」273〜281頁

解答例(C++)

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

int n;
int graph[100][100];
int d[100];
int f[100];

// 時刻
int cnt;

// 0:未探索 1:探索中 2:探索終わり
int visited[100];

void dfs(int i) {
  // 探索開始
  visited[i] = 1;
  d[i] = ++cnt;
  for (int j = 0; j < n; j++) {
    if (graph[i][j] == 0) {
      continue;
    }
    // 再帰
    if (visited[j] == 0) {
      dfs(j);
    }
  }
  visited[i] = 2;
  f[i] = ++cnt;
}

int main() {

  cin >> n;

  // 各変数を初期化
  cnt = 0;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      graph[i][j] = 0;
    }
    visited[i] = 0;
    d[i] = 0;
    f[i] = 0;
  }

  // 入力を受け取る
  for(int i = 0; i < n; i++) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; j++) {
      int v;
      cin >> v;
      graph[u - 1][v - 1] = 1;
    }
  }

  // 探索
  for (int i = 0; i < n; i++) {
    if(visited[i] == 0) {
      dfs(i);
    }
  }

  // 探索結果を出力
  for (int i = 0; i < n; i++) {
    cout << i + 1 << " " << d[i] << " " << f[i] << endl;
  }

  return 0;

}