Реши задачу на c++ Задача J. План Б Ограничение по...

Решать будем через точки сочленения (articulation points).

Идея

Для города $s$:

• Протест начинается в $s$, армия не может проходить через $s$.
• Город $s$ окружён, если в каждом его соседнем городе можно поставить военных.
• Это значит: если удалить вершину $s$ из графа, каждый сосед $s$ должен лежать в такой компоненте связности, где есть хотя бы одна база.

Город критичен, если

• в нём нет базы, и
• хотя бы одна из компонент графа после удаления этого города не содержит базы
  (тогда соседи из этой компоненты недостижимы, их не окружить).

Замечания:

• Если вершина не является точкой сочленения, то при её удалении граф остаётся связным ⇒ все вершины (включая соседей) попадают в одну компоненту.
  Так как баз хотя бы одна (по условию $b \ge 1$) и город сам без базы, то в этой компоненте есть база ⇒ такой город не критичен.
• Значит, критичными могут быть только точки сочленения без базы.

Как посчитать быстро

Сделаем один DFS (Таръян):

• tin[v] — время входа в DFS,
• low[v] — минимальное tin вершины, достижимой из поддерева v по одному дереву DFS + одному обратному ребру,
• стандартное правило: вершина u — точка сочленения, если:
  • она — корень DFS и у неё ≥ 2 ребёнка, или
  • она не корень, и есть ребёнок v такой, что low[v] >= tin[u].

Параллельно считаем:

• subtreeBase[v] — количество баз в поддереве v дерева DFS.
• Для каждой вершины u храним список childComps[u] — числа баз в тех поддеревьях детей v, которые образуют отдельные компоненты после удаления u:
  • для некорня: добавляем subtreeBase[v], если low[v] >= tin[u];
  • для корня: каждое поддерево ребёнка — отдельная компонента после удаления корня, поэтому добавляем для всех детей.

Пусть totalBases — общее число городов с базами.

Тогда для города u:

• если в u есть база — он по условию не критичен, пропускаем;
• если u — корень DFS:
  • если детей ≤ 1 → не точка сочленения → не критичен;
  • иначе компоненты — это поддеревья всех детей, их количества баз у нас в childComps[u].
    Если есть компонентa с 0 баз ⇒ u критичен.
• если u — некорень:
  • если childComps[u] пустой → u не точка сочленения → не критичен;
  • компоненты после удаления u:
    • для каждого записи x в childComps[u] — отдельная «дочерняя» компонента с x базами;
    • «родительская» компонента (всё остальное) содержит
      parentBases = totalBases - (есть ли база в u) - sum(childComps[u]).
  • Если хотя бы одна из этих компонент (любая x из childComps[u] или parentBases) равна 0, то u — критичен.

Сложность:
DFS по графу $O(n + m)$, памяти тоже $O(n + m)$, что подходит под ограничения.

---

Реализация на C++

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, b;
    if (!(cin >> n >> m >> b)) return 0;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<bool> isBase(n + 1, false);
    int totalBases = 0;
    for (int i = 0; i < b; ++i) {
        int x;
        cin >> x;
        if (!isBase[x]) {        // на всякий случай, вдруг дубликаты
            isBase[x] = true;
            ++totalBases;
        }
    }

    vector<int> tin(n + 1, 0), low(n + 1, 0), parent(n + 1, -1);
    vector<int> subtreeBase(n + 1, 0), rootChildren(n + 1, 0);
    vector<bool> used(n + 1, false);
    vector<vector<int>> childComps(n + 1);  // количества баз в отделившихся поддеревьях

    int timer = 0;

    function<void(int,int)> dfs = [&](int u, int p) {
        used[u] = true;
        parent[u] = p;
        tin[u] = low[u] = ++timer;
        subtreeBase[u] = isBase[u] ? 1 : 0;

        int children = 0;

        for (int v : g[u]) {
            if (v == p) continue;
            if (used[v]) {
                // обратное ребро
                low[u] = min(low[u], tin[v]);
            } else {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                subtreeBase[u] += subtreeBase[v];
                ++children;

                if (p == -1) {
                    // корень: каждое поддерево ребёнка - отдельная компонента после удаления корня
                    childComps[u].push_back(subtreeBase[v]);
                } else if (low[v] >= tin[u]) {
                    // отделившаяся компонента
                    childComps[u].push_back(subtreeBase[v]);
                }
            }
        }

        if (p == -1) {
            rootChildren[u] = children;
        }
    };

    // Граф по условию связный, но на всякий случай обойдём все компоненты
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) dfs(i, -1);
    }

    vector<int> critical;

    for (int u = 1; u <= n; ++u) {
        if (isBase[u]) continue;  // по условию такие города не критичны

        if (parent[u] == -1) {
            // корень DFS
            if (rootChildren[u] <= 1) continue;  // не точка сочленения

            bool bad = false; // есть ли компонента без базы
            for (int x : childComps[u]) {
                if (x == 0) {
                    bad = true;
                    break;
                }
            }
            if (bad) critical.push_back(u);
        } else {
            // некорень
            if (childComps[u].empty()) continue; // не точка сочленения

            long long sumChild = 0;
            bool bad = false;

            for (int x : childComps[u]) {
                sumChild += x;
                if (x == 0) bad = true; // дочерняя компонента без базы
            }

            int parentBases = totalBases - (isBase[u] ? 1 : 0) - (int)sumChild;
            if (parentBases == 0) bad = true;    // родительская компонента без базы

            if (bad) critical.push_back(u);
        }
    }

    sort(critical.begin(), critical.end());

    cout << critical.size() << "\n";
    if (!critical.empty()) {
        for (size_t i = 0; i < critical.size(); ++i) {
            if (i) cout << ' ';
            cout << critical[i];
        }
        cout << "\n";
    } else {
        cout << "\n"; // вторая строка пустая
    }

    return 0;
}

Если хочешь, могу отдельно нарисовать маленький пример и пошагово показать, как для него работают tin/low и подсчёт баз по компонентам.