はじめに
今回は深さ優先探索の4問をやりました！
精選100問はこちら！
24 ALDS_11_B - 深さ優先探索
問題はこちらです！
問題文↓
グラフを与えるので、小さい順にDFSしてください
基本問題でした！
コードは以下のようになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; // DFSのテンプレ. vector<bool> seen; vector<int> first_order; vector<int> last_order; void dfs(const vector<vector<ll>> &G, int v, int &ptr) { first_order[v] = ptr; ptr++; seen[v] = true; for (auto next_v : G[v]) { if (seen[next_v]) continue; dfs(G, next_v, ptr); } last_order[v] = ptr; ptr++; } int main() { // 入力. int n; cin >> n; vector<vector<ll>> G(n); rep(i, n) { int u, k; cin >> u >> k; rep(j, k) { int x; cin >> x; G[u - 1].push_back(x - 1); } } // DFSセットアップ. seen.assign(n, false); first_order.resize(n); last_order.resize(n); int ptr = 0; // 全ての頂点に対して、行ったことがなければDFS→頂点1から離れている木も探索. rep(i, n) { if (!seen[i]) { dfs(G, i, ptr); } } // 結果出力. for (int v = 0; v < n; ++v) cout << v + 1 << " " << first_order[v] + 1 << " " << last_order[v] + 1 << endl; return 0; }
けんちょんさんの記事がわかりやすい！
参考はこちらです！(参考)
25 AOJ 1160 - 島はいくつある？
問題はこちらです！
問題文↓
2次元平面上に陸と海が書かれています 斜めも入れて8方向に進むことが出来る場合、島の個数はいくつになりますか？
これは、DFSをして、1回目のDFSの回数をカウントしていくだけですね！
コードはこのようになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int w, h; vector<vector<bool>> seen; vector<vector<int>> A; vector<pair<int, int>> directions = {pair(1, -1), pair(0, -1), pair(-1, -1), pair(1, 0), pair(-1, 0), pair(1, 1), pair(0, 1), pair(-1, 1)}; void dfs(int i, int j) { seen[i][j] = true; rep(k, 8) { int x = directions[k].first; int y = directions[k].second; if (i + x >= 0 && i + x < h && j + y >= 0 && j + y < w) { if (!seen[i + x][j + y] && A[i + x][j + y]) { dfs(i + x, j + y); } } } } int main() { cin >> w >> h; while (!(w == 0 && h == 0)) { int cnt = 0; A.assign(h, vector<int>(w, 0)); seen.assign(h, vector<bool>(w, false)); rep(i, h) { rep(j, w) { cin >> A[i][j]; } } rep(i, h) { rep(j, w) { if (!seen[i][j] && A[i][j]) { dfs(i, j); cnt++; } } } cin >> w >> h; cout << cnt << endl; } return 0; }
resizeとassignの違いを知ることができた！
向きは配列に入れて管理が一番スマートだと思います！
26 AtCoder Beginner Contest 138 D - Ki
問題はこちらです！
問題文↓
1 から N までの番号がついた N 個の頂点を持つ根付き木が与えられ、それぞれ、初期値が0のカウンターを持っています この木の根は頂点1とします いくつかのクエリが与えられるので、ある頂点を根とする部分木に含まれるすべての頂点のカウンターに値を足してください
3ペナになったけれど、行けた！
1ペナ目:根が頂点1であることを見ずに、すべての頂点に対してDFSをした結果TLE
2ペナ目:頂点1のみにDFSをしたけれど、頂点1に対してつながっていない頂点のカウンターの値が出力されていなかった
3ペナ目:after contestのせいで死んだ→1に直接的にはつながっていないノードが存在したときにうまく行っていなかった
てことでこんなコードを書きました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; // 変数. int n, q; vector<vector<int>> G; vector<int> dat; vector<bool> seen; // DFS. void dfs(int now, int item) { dat[now] = item; seen[now] = true; rep(i, G[now].size()) { if (!seen[G[now][i]]) dfs(G[now][i], item + dat[G[now][i]]); } } int main() { // 入力. cin >> n >> q; G.resize(n); dat.resize(n, 0); seen.resize(n, false); // 無向グラフとしてグラフを作成. rep(i, n - 1) { int x, y; cin >> x >> y; G[x - 1].push_back(y - 1); G[y - 1].push_back(x - 1); } // 親の頂点に対して加算しておき、後で部分木に加算していく. rep(i, q) { int x, y; cin >> x >> y; dat[x - 1] += y; } // 根1に対してDFS. dfs(0, dat[0]); // 全て出力. rep(i, n) { cout << dat[i] << endl; } return 0; }
27 JOI 2009 予選 4 - 薄氷渡り
問題はこちらです！
問題文↓
陸と海に分けられた地図が与えられます 陸続きになっているとき、最大で何マス移動できますか？ 移動方法は4方向とします
DFSを全てのマスについて行えば制約が小さいので、実行時間に間に合います！
このようなコードを書きました！
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int h, w, ans = 0; vector<vector<int>> M; vector<vector<bool>> seen; vector<pair<int, int>> direction = { pair(1, 0), pair(-1, 0), pair(0, 1), pair(0, -1), }; void dfs(int i, int j, int now) { seen[i][j] = true; now++; ans = max(ans, now); rep(k, 4) { int ni = i + direction[k].first; int nj = j + direction[k].second; if (0 <= ni && ni < h && 0 <= nj && nj < w) { if (!seen[ni][nj] && M[ni][nj]) { dfs(ni, nj, now); } } } seen[i][j] = false; } int main() { cin >> w >> h; M.resize(h, vector<int>(w)); seen.resize(h, vector<bool>(w, false)); rep(i, h) { rep(j, w) cin >> M[i][j]; } rep(i, h) { rep(j, w) { if (M[i][j]) { seen.assign(h, vector<bool>(w, false)); dfs(i, j, 0); } } } cout << ans << endl; return 0; }
JOIはいい問題ですねー！
さいごに
最後まで読んでくださりありがとうございました！
ではまた！
