思路与算法

先按边编号迭代Tarjan找桥，并把非桥边连成的块用并查集收缩。非桥无论是否看守都不影响军营互通，贡献自由因子2^(m-桥数)。桥块树中，块内建营有2^size-1种非空选择。对子树维护E无军营、F非空且无外部军营、G非空且假定外部有军营三种计数。合并孩子v时：E新=2EEv，F新=2FEv+2EFv+GGv，G新=2GEv+EGv+G*Gv。根F乘自由因子。

正确性说明

攻击非桥不会断开原图，守或不守均合法。桥被切后，只在两侧都有军营时必须看守，否则两种选择都允许。E合并空孩子边自由选2种；F一侧为空时连接桥不分隔两个军营集，用无外部状态并乘2，两侧非空则桥必须守且两子状态都须按有外部军营计算，所以用G*Gv。G中已知外部有军营，非空孩子与外部之间的桥必须守，无军营孩子仍自由。三类互斥穷尽，初始块非空营的选择数准确，归纳得到所有方案且排除全空营。

复杂度

O(n+m+n log n)时间、O(n+m)空间；其中每个桥块计算2^size用快速幂，保守计O(n log n)。包括Tarjan、并查集、块树与三态数组初始化。

易错点

至少一座军营，但可以不守任何边。不能把所有桥都固定看守：只有分隔两个非空军营侧的桥必须守。用迭代DFS承受500000点深链，非桥边看守选择仍须计数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, int b) {
    long long v = 1;
    while (b) {
        if (b & 1)
            v = v * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return v;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> U(m), V(m);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        cin >> U[i] >> V[i];
        --U[i];
        --V[i];
        g[U[i]].push_back(i);
        g[V[i]].push_back(i);
    }
    vector<int> dfn(n), low(n), parent(n, -1), edge(n, -1), iter(n);
    vector<char> bridge(m);
    vector<int> stack{0};
    int timer = 0;
    dfn[0] = low[0] = ++timer;
    while (!stack.empty()) {
        int u = stack.back();
        if (iter[u] < (int)g[u].size()) {
            int e = g[u][iter[u]++];
            if (e == edge[u])
                continue;
            int v = U[e] ^ V[e] ^ u;
            if (!dfn[v]) {
                parent[v] = u;
                edge[v] = e;
                dfn[v] = low[v] = ++timer;
                stack.push_back(v);
            } else
                low[u] = min(low[u], dfn[v]);
        } else {
            stack.pop_back();
            if (parent[u] >= 0) {
                int p = parent[u];
                low[p] = min(low[p], low[u]);
                if (low[u] > dfn[p])
                    bridge[edge[u]] = 1;
            }
        }
    }
    vector<int> p(n), weight(n, 1);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    };
    for (int i = 0; i < m; i++)
        if (!bridge[i]) {
            int a = find(U[i]), b = find(V[i]);
            if (a != b) {
                if (weight[a] > weight[b])
                    swap(a, b);
                p[a] = b;
                weight[b] += weight[a];
            }
        }
    vector<vector<int>> tree(n);
    int B = 0;
    for (int i = 0; i < m; i++)
        if (bridge[i]) {
            int a = find(U[i]), b = find(V[i]);
            tree[a].push_back(b);
            tree[b].push_back(a);
            B++;
        }
    int root = find(0);
    vector<int> order{root}, par(n, -1);
    par[root] = root;
    for (int i = 0; i < (int)order.size(); i++)
        for (int v : tree[order[i]])
            if (v != par[order[i]]) {
                par[v] = order[i];
                order.push_back(v);
            }
    vector<long long> E(n, 1), F(n), G(n);
    for (int z = (int)order.size() - 1; z >= 0; z--) {
        int u = order[z];
        F[u] = G[u] = (power(2, weight[u]) + MOD - 1) % MOD;
        for (int v : tree[u])
            if (par[v] == u) {
                long long ff = (F[u] * (2 * E[v] % MOD) + E[u] * (2 * F[v] % MOD) + G[u] * G[v]) %
                               MOD,
                          gg = (G[u] * (2 * E[v] % MOD) + E[u] * G[v] + G[u] * G[v]) % MOD;
                E[u] = E[u] * (2 * E[v] % MOD) % MOD;
                F[u] = ff;
                G[u] = gg;
            }
    }
    cout << F[root] * power(2, m - B) % MOD << "\n";
}