Embercode: AI-powered software engineer course

1. In a DFS tree, which test on a child w of vertex v shows that the tree edge v-w is a bridge?

low[w] >= disc[v]disc[w] > disc[v]low[w] > disc[v]low[w] < low[v]

2. When is the start vertex of the DFS a cut vertex?

It has at least two children in the DFS treeIt has at least two neighboursIts low value is smaller than every other vertex'sIt has a back edge that leads to itself

3. What does this program print? ``

cpp
#include <iostream>
#include <utility>
#include <vector>

// Count the connected pieces, leaving out the edge with index skip.
int pieces(int n, const std::vector<std::pair<int, int>>& edges, int skip) {
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
        if (i == skip) continue;
        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }
    std::vector<bool> seen(n, false);
    int count = 0;
    for (int s = 0; s < n; ++s) {
        if (seen[s]) continue;
        ++count;
        std::vector<int> stack{s};
        seen[s] = true;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            for (int w : adj[v]) {
                if (!seen[w]) {
                    seen[w] = true;
                    stack.push_back(w);
                }
            }
        }
    }
    return count;
}

int main() {
    std::vector<std::pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}};
    int bridges = 0;
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
        if (pieces(5, edges, i) > pieces(5, edges, -1)) ++bridges;
    }
    std::cout << "bridges: " << bridges << '\n';
}

``

bridges: 1bridges: 2bridges: 3bridges: 5

4. What does this program print? ``

cpp
#include <iostream>
#include <utility>
#include <vector>

// Count the connected pieces, leaving out the edge with index skip.
int pieces(int n, const std::vector<std::pair<int, int>>& edges, int skip) {
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
        if (i == skip) continue;
        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }
    std::vector<bool> seen(n, false);
    int count = 0;
    for (int s = 0; s < n; ++s) {
        if (seen[s]) continue;
        ++count;
        std::vector<int> stack{s};
        seen[s] = true;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            for (int w : adj[v]) {
                if (!seen[w]) {
                    seen[w] = true;
                    stack.push_back(w);
                }
            }
        }
    }
    return count;
}

int main() {
    std::vector<std::pair<int, int>> edges = {{0, 1}, {0, 1}, {1, 2}};
    std::cout << "bridges:";
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
        if (pieces(3, edges, i) > pieces(3, edges, -1)) {
            std::cout << ' ' << edges[i].first << '-' << edges[i].second;
        }
    }
    std::cout << '\n';
}

``

bridges: 0-1 0-1 1-2bridges: 0-1bridges: 0-1 1-2bridges: 1-2

5. Which comparison does the cut vertex test use for a non-root vertex v and child w: low[w] ? disc[v]? Write only the symbol.

Type your answer.

Bridges