【アルゴリズム】深さ優先探索(DFS)

深さ優先探索(DFS)とは、木のデータ構造に対して、深さ優先で探索するアルゴリズムです。

略記でDFS(deep first search)と呼ばれます。

AtCorderでDFS系の問題出て、上手く解けなかったので勉強しながら理解した事と解法まとめました。同系統の問題や気づき等あれば加筆していきます。

DFSが問われた問題。

https://atcoder.jp/contests/agc035/tasks/agc035_b

閉路を持つグラフの場合も、既に訪れた事のあるノードはスルーするなど適切に処理すれば、根付き木として考えることができます。

よって、問題で与えられるグラフを根付き木として捉え、深いノードから順に偶数となるように向きの数を決めていけば回答となります。深さ順の探索となるため、DFSを用います。

最初に考えないといけない事は、ツリーをどのように表現するかだと思います。

とりあえずvector<vector<int> >でツリーのデータ構造としました。

次に深さ優先探索アルゴリズムの実装です。

調べた感じ再帰を使った実装とスタックを使った実装があるようです。

今回は再帰の方式を採用し、ルートノードを0と過程して、0→1から始まる深さ優先探索としてDFSを実装しました。戻り値として、そのノードが持っている向きの数が奇数かどうかのフラグを返します。

探索のステータスとして、未探索、探索中、探索済の3つのステータスを用意します。

訪問したノードは、探索中のステータスに変更します。訪問したノードが持っているノード(子ノード)を全て走査し、ステータスに応じて処理を分けます。子ノードを走査し終えると、ステータスを探索済みとします。

ケース１親ノードの場合

親ノードと子ノードが一致する場合は、逆に辿る事になるのでスルーします。

ケース２ステータスが探索済

ステータスが探索済の場合は、スルーします。

ケース３ステータスが探索中

ステータスが探索中の場合は、閉路の場合です。無限ループとなるためスルーします。今回の問題では、向きを定める必要があるため、訪問中ノードから対象の子ノードに対して向きを伸ばし、偶奇のフラグも反転させます。

ケース４

ステータスが未探索の場合は、対象の子ノードを探索します。子ノードの探索結果は、子ノードを始点とする向きの数が偶数なら0、奇数なら1を返します。

偶数ならば、子ノードを始点とした向きを追加する事はできません。探索済みのノードは、後の探索で一切触らないため、ここで子ノードを始点とした向きの数を増やした場合、全てのノードを偶数に寄せることが不可能となるためです。よって、訪問中のノードから子ノードに向きを定めることにします。訪問中ノードの向きの数が増えるため偶奇のフラグも反転させます。

奇数ならば、探索済みのノードは、後の探索で一切触らないため、ここで子ノードを始点とした向きの数を偶数に揃えなければ、全てのノードを偶数に寄せることが不可能となります。よって、子ノードを始点とした向きを定めます。

以上をコードにすると、以下のようになりました。

解法

#include <bits/stdc++.h>

using namespace std;
enum Status{
  NotExplore = 0,
  Exploring,
  Explored,
};

vector<vector<int> > tree(100000);
vector<Status> nodeStatus(100000);
vector<pair<int, int> > ans;

/// deep first search
int dfs (int currentNode, int parentNode)
{
  int isOdd = 0;
  nodeStatus[currentNode] = Status::Exploring;
  
  for (auto childNode : tree[currentNode]) {
    if (parentNode == childNode) continue;
    if (nodeStatus[childNode] == Status::Explored) continue;
    if (nodeStatus[childNode] == Status::Exploring) {
      isOdd ^= 1;
      ans.push_back({currentNode, childNode});
    }
    if (nodeStatus[childNode] == Status::NotExplore) {
      if (dfs(childNode, currentNode)) {
        ans.push_back({childNode, currentNode});
      } else {
        isOdd ^= 1;
        ans.push_back({currentNode, childNode});
      }
    }
  }

  nodeStatus[currentNode] = Status::Explored;
  return isOdd;
}

int main()
{
  int N, M; cin >> N >> M;
  
  for (int i=0; i<M; i++) {
    int a, b; cin >> a >> b;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  
  if (dfs(1, 0)) {
    cout << -1 << endl;
  } else {
    for (auto p : ans) {
      cout << p.first << " " << p.second << endl;
    }
  }
}

#include <bits/stdc++.h>

using namespace std;

enum Status{

NotExplore = 0,

Exploring,

Explored,

};

vector<vector<int> > tree(100000);

vector<Status> nodeStatus(100000);

vector<pair<int, int> > ans;

/// deep first search

int dfs (int currentNode, int parentNode)

{

int isOdd = 0;

nodeStatus[currentNode] = Status::Exploring;

for (auto childNode : tree[currentNode]) {

if (parentNode == childNode) continue;

if (nodeStatus[childNode] == Status::Explored) continue;

if (nodeStatus[childNode] == Status::Exploring) {

isOdd ^= 1;

ans.push_back({currentNode, childNode});

}

if (nodeStatus[childNode] == Status::NotExplore) {

if (dfs(childNode, currentNode)) {

ans.push_back({childNode, currentNode});

} else {

isOdd ^= 1;

ans.push_back({currentNode, childNode});

}

nodeStatus[currentNode] = Status::Explored;

return isOdd;

}

int main()

{

int N, M; cin >> N >> M;

for (int i=0; i<M; i++) {

int a, b; cin >> a >> b;

tree[a].push_back(b);

tree[b].push_back(a);

}

if (dfs(1, 0)) {

cout << -1 << endl;

} else {

for (auto p : ans) {

cout << p.first << " " << p.second << endl;

}

Pocket