DFS - Tree and Graph Properties

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// This example demonstrates:
5
// 1) Computing DFS entry times (tin), exit times (tout_exit), and subtree sizes (sz)
6
// 2) Flattening a tree so each subtree is a contiguous range in an array
7
// 3) Answering static subtree sum queries using a prefix sum over the Euler array
8
// Note: For dynamic updates, replace prefix with a Fenwick/Segment Tree.
9
10
const int MAXN = 200000; // adjust as needed
11
vector<int> g[MAXN + 5];
12
int n;
13
vector<long long> val;         // node values (1-indexed)
14
vector<int> tin, tout_exit, sz;// timestamps and subtree sizes
15
vector<int> euler;             // euler[pos] = value of node at position pos
16
int timer_dfs = 0;
17
18
void dfs(int u, int p) {
19
    tin[u] = ++timer_dfs; // discovery time / position in flattened array
20
    sz[u] = 1;
21
    euler[tin[u]] = (int)val[u];
22
    for (int v : g[u]) {
23
        if (v == p) continue; // important for undirected trees: ignore parent
24
        dfs(v, u);
25
        sz[u] += sz[v];
26
    }
27
    tout_exit[u] = ++timer_dfs; // classic exit time (not used as right boundary here)
28
}
29
30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
34
    // Example input format:
35
    // n
36
    // val[1..n]
37
    // n-1 edges u v (1-indexed, undirected, forms a tree)
38
    // q
39
    // q lines: node u for subtree sum query
40
    // Sample:
41
    // 7
42
    // 1 2 3 4 5 6 7
43
    // 1 2
44
    // 1 3
45
    // 2 4
46
    // 2 5
47
    // 3 6
48
    // 3 7
49
    // 3
50
    // 1
51
    // 2
52
    // 3
53
54
    if (!(cin >> n)) return 0;
55
    val.assign(n + 1, 0);
56
    for (int i = 1; i <= n; ++i) cin >> val[i];
57
    for (int i = 1; i <= n; ++i) g[i].clear();
58
    for (int i = 0; i < n - 1; ++i) {
59
        int u, v; cin >> u >> v;
60
        g[u].push_back(v);
61
        g[v].push_back(u);
62
    }
63
64
    tin.assign(n + 1, 0);
65
    tout_exit.assign(n + 1, 0);
66
    sz.assign(n + 1, 0);
67
    euler.assign(n + 2, 0); // 1..n used; +2 for safety
68
    timer_dfs = 0;
69
70
    int root = 1; // assume 1 is the root
71
    dfs(root, -1);
72
73
    // Build prefix sums over Euler array using subtree range [tin[u], tin[u] + sz[u] - 1]
74
    vector<long long> pref(n + 2, 0);
75
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + (long long)euler[i];
76
77
    auto subtree_sum = [&](int u) {
78
        int L = tin[u];
79
        int R = tin[u] + sz[u] - 1; // right boundary from subtree size
80
        return pref[R] - pref[L - 1];
81
    };
82
83
    // Optional: function to check if u is ancestor of v using classic times
84
    auto is_ancestor = [&](int u, int v) {
85
        return tin[u] < tin[v] && tout_exit[v] < tout_exit[u];
86
    };
87
88
    int q; cin >> q;
89
    while (q--) {
90
        int u; cin >> u;
91
        cout << subtree_sum(u) << "\n";
92
    }
93
94
    // Example: check ancestry (not part of required output)
95
    // cerr << (is_ancestor(1, 4) ? "1 is ancestor of 4\n" : "not ancestor\n");
96
97
    return 0;
98
}
99

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Detect a cycle in a directed graph using DFS colors:
5
// 0 = unvisited (white), 1 = in recursion stack (gray), 2 = finished (black).
6
// On seeing an edge to a gray node, we have a back edge and can reconstruct a cycle.
7
8
int n, m;
9
vector<vector<int>> g;
10
vector<int> color, parent;
11
int start_cycle = -1, end_cycle = -1;
12
13
bool dfs(int u) {
14
    color[u] = 1; // gray
15
    for (int v : g[u]) {
16
        if (color[v] == 0) {
17
            parent[v] = u;
18
            if (dfs(v)) return true;
19
        } else if (color[v] == 1) {
20
            // back edge u -> v found; cycle exists
21
            start_cycle = v; // cycle start
22
            end_cycle = u;   // current node
23
            return true;
24
        }
25
    }
26
    color[u] = 2; // black
27
    return false;
28
}
29
30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
34
    // Input:
35
    // n m
36
    // m edges: u v (directed)
37
    // Prints a cycle if exists, else ACYCLIC
38
39
    if (!(cin >> n >> m)) return 0;
40
    g.assign(n + 1, {});
41
    for (int i = 0; i < m; ++i) {
42
        int u, v; cin >> u >> v;
43
        g[u].push_back(v);
44
    }
45
46
    color.assign(n + 1, 0);
47
    parent.assign(n + 1, -1);
48
49
    bool has_cycle = false;
50
    for (int u = 1; u <= n; ++u) {
51
        if (color[u] == 0 && dfs(u)) { has_cycle = true; break; }
52
    }
53
54
    if (!has_cycle) {
55
        cout << "ACYCLIC\n";
56
        return 0;
57
    }
58
59
    // Reconstruct the cycle: walk from end_cycle up to start_cycle using parents
60
    vector<int> cycle;
61
    cycle.push_back(start_cycle);
62
    for (int v = end_cycle; v != start_cycle; v = parent[v]) cycle.push_back(v);
63
    cycle.push_back(start_cycle);
64
    reverse(cycle.begin(), cycle.end());
65
66
    cout << "CYCLE FOUND (length = " << (int)cycle.size() - 1 << "):\n";
67
    for (size_t i = 0; i < cycle.size(); ++i) {
68
        cout << cycle[i] << (i + 1 == cycle.size() ? '\n' : ' ');
69
    }
70
    return 0;
71
}
72

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Kosaraju's algorithm:
5
// 1) DFS on G to compute order by finish times.
6
// 2) DFS on reversed graph in reverse order to extract SCCs.
7
8
int n, m;
9
vector<vector<int>> g, gr; // graph and reversed graph
10
vector<int> used;
11
vector<int> order, comp; // order by finish time; comp[v] = component id
12
13
void dfs1(int u) {
14
    used[u] = 1;
15
    for (int v : g[u]) if (!used[v]) dfs1(v);
16
    order.push_back(u); // push after exploring: this is by increasing finish time
17
}
18
19
void dfs2(int u, int cid) {
20
    comp[u] = cid;
21
    for (int v : gr[u]) if (comp[v] == -1) dfs2(v, cid);
22
}
23
24
int main() {
25
    ios::sync_with_stdio(false);
26
    cin.tie(nullptr);
27
28
    // Input:
29
    // n m
30
    // m edges u v (directed)
31
    // Output: number of SCCs and the component id of each vertex (1..k)
32
33
    if (!(cin >> n >> m)) return 0;
34
    g.assign(n + 1, {});
35
    gr.assign(n + 1, {});
36
    for (int i = 0; i < m; ++i) {
37
        int u, v; cin >> u >> v;
38
        g[u].push_back(v);
39
        gr[v].push_back(u); // reversed edge
40
    }
41
42
    used.assign(n + 1, 0);
43
    order.clear();
44
45
    for (int u = 1; u <= n; ++u) if (!used[u]) dfs1(u);
46
47
    comp.assign(n + 1, -1);
48
    int cid = 0;
49
    for (int i = (int)order.size() - 1; i >= 0; --i) {
50
        int u = order[i];
51
        if (comp[u] == -1) dfs2(u, ++cid);
52
    }
53
54
    cout << cid << "\n"; // number of SCCs
55
    for (int u = 1; u <= n; ++u) cout << comp[u] << (u == n ? '\n' : ' ');
56
    return 0;
57
}
58