这道题之前做过一次,我们来转换一下这道题的题意，题中给到了边、点我们可以想到强连通分量，进而想到tarjan算法。通过所给样例及题意，我们可以将原题目转化为以下内容：
给定一张图，选择一些点和边，使得割断任意没有选的边，被选中的点仍联通，最终答案对 1 0 9 + 7 10^9+7 109+7取模。
想做这道题，我们得先知道什么是割点、割边（桥）、缩边、双连通分量
看到图和连通，想到tarjan。割断一条没有选的边，选中的点仍连通，割非割边，整张图仍然连通。
把割边删掉，则整张图分成若干连通子图。可以把一张子图看成一个点，这样形成的新图上没有环，因为在环上的边都不是割边，那它就是一棵树。使用vector邻接表建图，dfs一遍，使用 f f f数组记录答案，最终将答案转移到 a n s ans ans上。
上一次做这道题代码愣是写了120行，昨天换了个思路，尝试着把dfs压缩了一下，代码就短多了。
code
//本质使得割掉一些边之后,剩下的点仍然联通
//看到连通块就想到tarjan算法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 500005;
const int mod = 1e9 + 7;
ll n, m;//城市个数,双向道路数量
ll ans;//方案数
//tarjan算法的常用数组
ll st[N], dfn[N], low[N],bl[N];
ll f[N];
vector<int>e[N], g[N];//使用vector为了方便
void tarjan(int x, int fa) {
st[++st[0]] = x;
dfn[x] = low[x] = ++dfn[0];
for (int y : e[x]){//从数组e中依次取出元素赋值给y
if (y != fa) {
if (!dfn[y]){
tarjan(y, x);
}
low[x] = min(low[x], low[y]);
}
}
if (dfn[x] == low[x]) {
m++;
while (st[st[0]] != x)bl[st[st[0]--]] = m;
bl[st[st[0]--]] = m;
}
}
void dfs(int k, int fa) {
ans = (ans + f[k]) % mod;
for (int i : g[k]){
if (i != fa) {
dfs(i, k);
f[i] = f[i] * (mod + 1) / 2 % mod;
ans = (ans + f[k] * f[i]) % mod;
f[k] = (f[k] + f[i] + f[k] * f[i]) % mod;
}
}
}
int main() {
cin >> n >> m;
//输入边+建图
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
//临接表建图
e[x].push_back(y);
e[y].push_back(x);
}
m = 0;
tarjan(1, 0);
for (int i = 1; i <= m; i++){
f[i]++;
}
for (int i = 1; i <= n; i++){
f[bl[i]] = f[bl[i]] * 2 % mod;
}
for (int i = 1; i <= m; i++){
f[i]--;
}
for (int i = 1; i <= n; i++){
for (int j : e[i]){
if (bl[i] != bl[j]){
g[bl[i]].push_back(bl[j]);
}
}
}
dfs(1, 0);
for (int i = 1; i <= n; i++){
for (int j : e[i]){
if (i < j){
ans = ans * 2 % mod;
}
}
}
cout << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int M = 4e6;
const int mod = 1e9 + 7;
int add(int x, int y) {
return ((x += y) >= mod) ? x - mod : x;
}
void addn(int &x, int y) {
if ((x += y) >= mod) x -= mod;
}
int mins(int x, int y) {
return ((x -= y) < 0) ? x + mod : x;
}
struct G {
struct edge {
int to, nxt, w;
} e[M << 1];
int head[M], cnt1 = 1;
void link(int u, int v) {
e[++cnt1] = {v, head[u], 1};
head[u] = cnt1;
}
} g1, g2;
int fa[M];
int dfn[M], low[M], cnt;
bool cut[M];
void tarjan(int u, int f) {
low[u] = dfn[u] = ++cnt;
for (int i = g1.head[u]; i; i = g1.e[i].nxt) {
int v = g1.e[i].to;
if (v == f) continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) g1.e[i].w = g1.e[i ^ 1].w = 0; // 0 标记为割边，i^1 用了成对变换的技巧，把反边一起标记
} else low[u] = min(low[u], dfn[v]);
}
}
int siz1[M], siz2[M];
bool vis[M];
int bl[M];
int n, m;//n城市个数,m双向道路数量
int cnt2;
// 用于划分连通块，siz1 对应行文中的 cntp，点数；siz2 对应行文中的 cnte，边数
void dfs2(int u, int f, int t) {
bl[u] = t;
vis[u] = 1;
++siz1[t];
for (int i = g1.head[u]; i; i = g1.e[i].nxt) {
if (g1.e[i].w) ++siz2[t];
int v = g1.e[i].to;
if (g1.e[i].w == 0 || v == f) continue;
if (!vis[v]) dfs2(v, u, t);
}
}
int sm[M];
// 用于计算文中的 sum 数组，子树中边数和，包括被缩掉者
void dfs4(int u, int fa) {
sm[u] = siz2[u];
for (int i = g2.head[u]; i; i = g2.e[i].nxt) {
int v = g2.e[i].to;
if (v == fa) continue;
dfs4(v, u);
sm[u] += sm[v] + 1;
}
}
int dp[M][2], pw[M], ans;
// 统计答案的 dfs，dp 意义如上文所叙
// dp_{u,0} 强制 u 及其子树不选任意一个点（空）
// dp_{u,1} 强制 u 及其子树选至少一个点，且所有被选的点与 u 连通（不空）。
void dfs3(int u, int fa) {
dp[u][0] = pw[siz2[u]];
dp[u][1] = 1ll * pw[siz2[u]] * (pw[siz1[u]] - 1) % mod;
int tot = 0;
for (int i = g2.head[u]; i; i = g2.e[i].nxt) {
int v = g2.e[i].to;
if (v == fa) continue;
dfs3(v, u);
dp[u][1] = add(1ll * dp[u][1] * add(1ll * dp[v][0] * 2 % mod, dp[v][1]) % mod, 1ll * dp[u][0] * dp[v][1] % mod);
dp[u][0] = 1ll * dp[u][0] * 2 % mod * dp[v][0] % mod;
addn(tot, dp[v][1]);
}
if (u != n + 1) addn(ans, 1ll * dp[u][1] * pw[sm[n + 1] - sm[u] - 1] % mod);
else addn(ans, 1ll * dp[u][1] % mod);
}
int find(int u) {
return u == fa[u] ? u : fa[u] = find(fa[u]);
}
void merge(int u, int v) {
if ((u = find(u)) != (v = find(v))) fa[u] = v;
}
int main() {
scanf("%d %d", &n, &m);
pw[0] = 1;
for (int i = 1; i <= 2 * n + m; i++) pw[i] = 1ll * pw[i - 1] * 2 % mod;
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g1.link(u, v);
g1.link(v, u);
}
tarjan(1, 0);
cnt2 = n;
for (int i = 1; i <= n; i++) if (!vis[i]) dfs2(i, 0, ++cnt2);
for (int i = n + 1; i <= 2 * n; i++) {
siz2[i] /= 2;
}
// 缩边
for (int i = 1; i <= 2 * n; i++) fa[i] = i;
for (int u = 1; u <= n; u++) {
for (int i = g1.head[u]; i; i = g1.e[i].nxt) {
int v = g1.e[i].to;
if (find(bl[u]) != find(bl[v])) g2.link(bl[u], bl[v]), g2.link(bl[v], bl[u]), merge(bl[u], bl[v]);
}
}
// n+1 是缩完边后树的根
dfs4(n + 1, 0);
dfs3(n + 1, 0);
printf("%d\n", ans);
}