【分野別 初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【深さ優先探索】

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の2-3. 分野別　初中級者が解くべき過去問精選 100 問を初級者がC++で解いていきます。

深さ優先探索

24　ALDS_11_B - 深さ優先探索

AIZU ONLINE JUDGE に登録していないので、後回し。

25　AOJ 1160 - 島はいくつある？

AIZU ONLINE JUDGE に登録していないので、後回し。

26　AtCoder Beginner Contest 138 D - Ki

順番に足していったら、たぶん間に合わない。加算する親部分に一時的に値を保持して、DFSを使って子に値を流し込んでいくイメージ。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

vector<vector<int>> tree(200001);
vector<int> val(200001, 0);

void dfs(int i, int j) {
  fore(t, tree.at(i)) {
    if(t != j){
      val.at(t) += val.at(i);
      dfs(t, i);
    }
  }
}

int main() {
  int N, Q;
  cin >> N >> Q;
  
  rep(i, 0, N - 1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    tree.at(a).push_back(b);
    tree.at(b).push_back(a);
  }
  
  rep(i, 0, Q) {
    int p, x;
    cin >> p >> x;
    val.at(p - 1) += x;
  }
  
  dfs(0, -1);
  rep(i, 0, N) cout << val.at(i) << " ";
}

27　JOI 2009 予選 4 - 薄氷渡り

純粋にDFSで深さを探るだけ。1マス戻るときに割った氷を復活させておかないと数え間違えてしまう。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
vector<vector<int>> ice, seen;
int m, n, ans = 0;

void dfs(int i, int j, int tmp) {
  tmp++;
  seen.at(i).at(j) = true;
  
  rep(dir, 0, 4) {
    int ni = i + dx.at(dir);
    int nj = j + dy.at(dir);
    
    if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
    if (ice.at(ni).at(nj) == 0) continue;
    if (seen.at(ni).at(nj)) continue;
    
    dfs(ni, nj, tmp);
  }
  ans = max(ans, tmp);
  tmp--;
  seen.at(i).at(j) = false;
}

int main() {
  cin >> m >> n;
  
  ice.assign(n, vector<int>(m));
  seen.assign(n, vector<int>(m));
  rep(i, 0, n) {
    rep(j, 0, m) cin >> ice.at(i).at(j);
  }
  
  rep(i, 0, n) {
    rep(j, 0, m) {
      if (!ice.at(i).at(j)) continue;
      int tmp = 0;
      dfs(i, j, tmp);
    }
  }
  cout << ans << endl;
}