C++(g++ 7.5.0) 解法, 执行用时: 1332ms, 内存消耗: 191856K, 提交时间: 2023-05-10 23:03:32

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const int mod = 19260817;
const int N = 4e6+10;
int h[N],e[N<<2],ne[N<<2],idx;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
int ins[N],tot,dfn[N],low[N];
int s[N],top;
int cnt,bel[N];
int sz[N];
void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot;
	s[++top]=u;
	ins[u]=true;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		if(!dfn[j])
		{
			tarjan(j,u);
			low[u]=min(low[u],low[j]);
		}
		else if(ins[j]) low[u]=min(low[u],dfn[j]);
	}
	if(dfn[u]==low[u])
	{
		cnt++;
		while(1)
		{
			int x=s[top--];
			bel[x]=cnt;
			sz[cnt]++;
			ins[x]=false;
			if(x==u) break;
		}
	}
}
ll dp[N];
ll f[N];
vector<int> edge[N];
void dfs(int u,int fa)
{
	dp[u]=0;
	f[u]=(sz[u]>1);
	for(auto x:edge[u])
	{
		if(x==fa) continue;
		dfs(x,u);
		dp[u]=(dp[u]+f[x]*f[u]+dp[x])%mod;
		f[u]=(f[u]+f[x]*(sz[u]>1?2:1))%mod;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			tarjan(i,-1);
		}
	}
	for(int u=1;u<=n;u++)
	{
		for(int i=h[u];~i;i=ne[i])
		{
			int j=e[i];
			int x=bel[j],y=bel[u];
			if(x!=y) edge[x].push_back(y);
		}
	}
	dfs(1,-1);
	cout<<dp[1]%mod<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 1736ms, 内存消耗: 133468K, 提交时间: 2020-01-27 00:13:52

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std;
typedef long long ll;
 
const int N = 1e6+10, P = 0x0125e591;
int n,m,ans,cnt,dep[N],fa[N];
int s[N],vis[N],dp[N];
vector<int> g[N],gg[N];
 
void get(int x, int y) {
    if (dep[x]<dep[y]) return;
    s[y]=++cnt,vis[cnt]=1;
    for (; x!=y; x=fa[x]) s[x]=cnt;
}
void dfs(int x, int f) {
    fa[x]=f,dep[x]=dep[f]+1;
    for (int y:g[x]) if (y!=f) {
        if (dep[y]) get(x,y);
        else dfs(y,x);
    }
}
void dfs2(int x, int f) {
    int t = vis[x]+1;
    dp[x] = vis[x];
    for (int y:gg[x]) if (y!=f) {
        dfs2(y,x);
        ans = (ans+(ll)dp[x]*dp[y])%P;
        dp[x] = (dp[x]+t*dp[y])%P;
    }
}
 
int main() {
    scanf("%d%d",&n,&m);
    REP(i,1,m) {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].pb(v),g[v].pb(u);
    }
    dfs(1,0);
    REP(i,1,n) if (!s[i]) s[i]=++cnt;
    REP(i,1,n) for (int j:g[i]) {
        int u=s[i],v=s[j];
        if (u!=v) gg[u].pb(v);
    }
    dfs2(1,0);
    if (ans<0) ans += P;
    printf("%d\n", ans);
}