链接:https://ac.nowcoder.com/acm/problem/14394
来源:牛客网
题目描述
给你一个连通无向图,保证每个点最多属于一个简单环,每个点度数最多为3,求这个图有多少“手铐图形个数”
其中“手铐图形个数”,定义为三元组(x,y,S),其中x和y表示图上的两个点,S表示一条x到y的简单路径,而且必须满足:
1.x和y分别在两个不同的简单环上
2.x所在的简单环与路径S的所有交点仅有x,y所在的简单环与路径S的所有交点仅有y。
(x,y,S)与(y,x,S)算同一个手铐
如果你无法理解,可以参考样例。
输入描述:
第一行两个数n和m
之后m行,每行两个数x,y表示x和y之间有一条边。
输出描述:
输出一个数,表示手铐的个数对19260817取模的结果
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<iomanip>
#include<vector>
using namespace std;
const int N=1e6+5,M=4e6+5,mod=19260817;
int nxt[M],head[N],go[M],tot=1;
inline void add(int u,int v){
nxt[++tot]=head[u],head[u]=tot,go[tot]=v;
nxt[++tot]=head[v],head[v]=tot,go[tot]=u;
}
int n,m;
inline int read(){
int x=0; char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
return x;
}
int dfn[N],low[N],co[N],st[N],si[N],col,num,top;
inline void Tarjan(int u,int fr){
dfn[u]=low[u]=++num;
st[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=go[i];
if(v==fr)continue;
if(!dfn[v]){
Tarjan(v,u);
low[u]=min(low[u],low[v]);
}else if(!co[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
co[u]=++col;
si[col]=1;
while(st[top]!=u){
co[st[top]]=col;
si[col]++;
--top;
}
--top;
}
}
struct node{
int u,v;
}e[M];
long long ans[N],f[N];
void DFS_dp(int x,int fa){
ans[x]=0;
if(si[x]>1)f[x]=1;
else f[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=go[i];
if(y==fa)continue;
DFS_dp(y,x);
ans[x]=(ans[x]+f[x]*f[y]%mod+ans[y])%mod;
if(si[x]>1)f[x]=(f[x]+f[y]*2)%mod;
else f[x]=(f[x]+f[y])%mod;
}
}
int main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
e[i]=(node){u,v};
add(u,v);
}
for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i,0);
memset(nxt,0,sizeof(nxt)),tot=1;
memset(head,0,sizeof(head));
for(int i=1;i<=m;i++){
if(co[e[i].u]==co[e[i].v])continue;
add(co[e[i].u],co[e[i].v]);
}
DFS_dp(1,0);
printf("%lld
",ans[1]);
}