Depth-First Search (DFS)

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Find connected components using DFS (recursive)
5
// Input format:
6
// n m
7
// m lines: u v (1-indexed undirected edges)
8
// Output: number of components and listing of each component's nodes
9
10
void dfs(int u, const vector<vector<int>>& g, vector<int>& comp, int cid) {
11
    comp[u] = cid; // mark component id (also serves as visited)
12
    for (int v : g[u]) {
13
        if (comp[v] == -1) {
14
            dfs(v, g, comp, cid);
15
        }
16
    }
17
}
18
19
int main() {
20
    ios::sync_with_stdio(false);
21
    cin.tie(nullptr);
22
23
    int n, m; 
24
    if (!(cin >> n >> m)) return 0;
25
    vector<vector<int>> g(n + 1);
26
    for (int i = 0; i < m; ++i) {
27
        int u, v; cin >> u >> v;
28
        g[u].push_back(v);
29
        g[v].push_back(u); // undirected
30
    }
31
32
    vector<int> comp(n + 1, -1);
33
    int cid = 0; // component counter starts from 0
34
35
    for (int u = 1; u <= n; ++u) {
36
        if (comp[u] == -1) {
37
            dfs(u, g, comp, cid);
38
            ++cid;
39
        }
40
    }
41
42
    cout << cid << "\n";
43
    // Collect vertices per component for display
44
    vector<vector<int>> groups(cid);
45
    for (int u = 1; u <= n; ++u) groups[comp[u]].push_back(u);
46
    for (int i = 0; i < cid; ++i) {
47
        cout << "component " << i << ":";
48
        for (int u : groups[i]) cout << ' ' << u;
49
        cout << '\n';
50
    }
51
    return 0;
52
}
53

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Iterative DFS that records preorder (discovery) and postorder (finish) sequences.
5
// Input:
6
// n m
7
// m lines: u v (1-indexed directed edges)
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    int n, m; 
14
    if (!(cin >> n >> m)) return 0;
15
    vector<vector<int>> g(n + 1);
16
    for (int i = 0; i < m; ++i) {
17
        int u, v; cin >> u >> v;
18
        g[u].push_back(v); // directed
19
    }
20
21
    vector<int> color(n + 1, 0); // 0=white,1=gray,2=black
22
    vector<int> preorder, postorder;
23
24
    // Stack stores (node, next_child_index). Simulates recursion.
25
    for (int s = 1; s <= n; ++s) if (color[s] == 0) {
26
        stack<pair<int,int>> st;
27
        st.push({s, 0});
28
        color[s] = 1; // gray (discovered)
29
        preorder.push_back(s);
30
        while (!st.empty()) {
31
            auto &[u, idx] = st.top();
32
            if (idx < (int)g[u].size()) {
33
                int v = g[u][idx++];
34
                if (color[v] == 0) {
35
                    color[v] = 1; // discover v
36
                    preorder.push_back(v);
37
                    st.push({v, 0});
38
                }
39
                // if color[v] != 0, skip; cycle handling is not needed for orders here
40
            } else {
41
                // finished u
42
                color[u] = 2; // black
43
                postorder.push_back(u);
44
                st.pop();
45
            }
46
        }
47
    }
48
49
    cout << "preorder:";
50
    for (int x : preorder) cout << ' ' << x;
51
    cout << '\n';
52
53
    cout << "postorder:";
54
    for (int x : postorder) cout << ' ' << x;
55
    cout << '\n';
56
    return 0;
57
}
58

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Topological sort using DFS finishing times. Detect cycles with colors.
5
// Input:
6
// n m
7
// m lines: u v (edge u -> v)
8
// Output: topological order or "IMPOSSIBLE" if a cycle exists.
9
10
vector<vector<int>> g;
11
vector<int> color; // 0=white, 1=gray, 2=black
12
vector<int> order;
13
bool hasCycle = false;
14
15
void dfs(int u) {
16
    color[u] = 1; // gray
17
    for (int v : g[u]) {
18
        if (color[v] == 0) {
19
            dfs(v);
20
            if (hasCycle) return; // early exit if desired
21
        } else if (color[v] == 1) {
22
            hasCycle = true; // back edge => cycle
23
            return;
24
        }
25
    }
26
    color[u] = 2; // black
27
    order.push_back(u); // push on finish
28
}
29
30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
34
    int n, m; 
35
    if (!(cin >> n >> m)) return 0;
36
    g.assign(n + 1, {});
37
    for (int i = 0; i < m; ++i) {
38
        int u, v; cin >> u >> v;
39
        g[u].push_back(v);
40
    }
41
42
    color.assign(n + 1, 0);
43
    for (int u = 1; u <= n; ++u) if (color[u] == 0) {
44
        dfs(u);
45
        if (hasCycle) break;
46
    }
47
48
    if (hasCycle) {
49
        cout << "IMPOSSIBLE\n";
50
    } else {
51
        reverse(order.begin(), order.end());
52
        for (int x : order) cout << x << ' ';
53
        cout << '\n';
54
    }
55
    return 0;
56
}
57

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Classify edges as tree, back, forward, or cross using DFS times.
5
// Input:
6
// n m
7
// m lines: u v (directed edges). We will also print classification for each input edge.
8
9
struct Edge { int u, v; };
10
11
vector<vector<int>> g;
12
vector<int> color, tin, tout;
13
int timer = 0;
14
15
void dfs(int u) {
16
    color[u] = 1; // gray
17
    tin[u] = ++timer; // discovery time
18
    for (int v : g[u]) {
19
        if (color[v] == 0) {
20
            cout << u << " -> " << v << ": tree\n";
21
            dfs(v);
22
        } else if (color[v] == 1) {
23
            cout << u << " -> " << v << ": back\n"; // to ancestor on stack
24
        } else {
25
            // color[v] == 2 (finished). Determine forward vs cross by interval nesting.
26
            if (tin[u] < tin[v] && tout[v] < tout[u]) {
27
                cout << u << " -> " << v << ": forward\n";
28
            } else {
29
                cout << u << " -> " << v << ": cross\n";
30
            }
31
        }
32
    }
33
    tout[u] = ++timer; // finish time set on exit
34
    color[u] = 2; // black
35
}
36
37
int main() {
38
    ios::sync_with_stdio(false);
39
    cin.tie(nullptr);
40
41
    int n, m; 
42
    if (!(cin >> n >> m)) return 0;
43
    g.assign(n + 1, {});
44
    vector<Edge> edges; edges.reserve(m);
45
    for (int i = 0; i < m; ++i) {
46
        int u, v; cin >> u >> v; edges.push_back({u,v}); g[u].push_back(v);
47
    }
48
49
    color.assign(n + 1, 0);
50
    tin.assign(n + 1, 0);
51
    tout.assign(n + 1, 0);
52
53
    for (int u = 1; u <= n; ++u) if (color[u] == 0) dfs(u);
54
55
    // Note: The classifications were printed during exploration when the relationship can be decided.
56
    return 0;
57
}
58