提交时间:2025-02-10 15:01:14
运行 ID: 374189
#include <iostream> #include <vector> #include <algorithm> const int MOD = 1e9 + 7; using namespace std; // 定义边的结构体 struct Edge { int to; int id; }; // 全局变量 int n, m; vector<vector<Edge>> graph; vector<int> dfn, low; vector<bool> is_bridge; int timestamp = 0; vector<int> component_size; // 深度优先搜索函数 void dfs(int u, int fa) { dfn[u] = low[u] = ++timestamp; int size = 1; for (const Edge& edge : graph[u]) { int v = edge.to; if (v == fa) continue; if (!dfn[v]) { dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) { is_bridge[edge.id] = true; } size += component_size.back(); } else { low[u] = min(low[u], dfn[v]); } } component_size.push_back(size); } // 快速幂函数 int quick_pow(int a, int b) { int res = 1; while (b) { if (b & 1) res = 1LL * res * a % MOD; a = 1LL * a * a % MOD; b >>= 1; } return res; } int main() { cin >> n >> m; graph.resize(n); dfn.resize(n, 0); low.resize(n, 0); is_bridge.resize(m, false); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; graph[u].push_back({v, i}); graph[v].push_back({u, i}); } dfs(0, -1); component_size.pop_back(); int ans = 1; for (int size : component_size) { ans = 1LL * ans * (quick_pow(2, size) - 1) % MOD; if (ans < 0) ans += MOD; } int bridge_count = 0; for (bool b : is_bridge) { if (b) ++bridge_count; } ans = 1LL * ans * quick_pow(2, bridge_count) % MOD; cout << ans << endl; return 0; }