[7.18NOIP模拟测试5]星际旅行 题解

题面(加密)

考场上靠打表yy出的规律进而想到的正解233333

可以把一条双向边拆成两条单向边，这样的话每个点度数都为偶数，符合欧拉图的定义。

那么题目可以转化为：去掉两条边，使图中存在一条欧拉路。

如果拆边还要满足欧拉路性质，就必须拆两条有公共顶点的边。

但是本题中明确给出含有自环，所以还有另外两种操作可以满足题意：

去掉两个自环，去掉一个自环一条边。

统计点的度数和自环数分类计算即可。

但是题中没有给图一定联通的条件，所以还要特判。

一定注意不能判点联通，点散一地没边连着对结果毫无影响.利用dfs或冰茶几判边联通即可。

//把命运交给打表找规律
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m;
int dg[N],po,fa[N],deg[N];
int findf(int x)
{
if(fa[x]==x)return x;
return fa[x]=findf(fa[x]);
}
void merge(int x,int y)
{
int fx=findf(x),fy=findf(y);
fa[fx]=fy;
}
long long ans,sumdeg;
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
if(x!=y)
dg[x]++,dg[y]++,merge(x,y);
else po++;
deg[x]++,deg[y]++;
}
int node=0;
for(int i=1;i<=n;i++)
if(deg[i])
{
findf(i);
node=i;
break;
}
for(int i=1;i<=n;i++)
{
if(deg[i]&&findf(i)!=fa[node])
{
puts("0");
return 0;
}
}
for(int i=1;i<=n;i++)
ans=ans+1LL*(dg[i]-1)*dg[i]/2,sumdeg+=1LL*dg[i];
long long ans1=1LL*po*sumdeg/2,ans2=1LL*po*(po-1)/2;
cout<<ans+ans1+ans2<<endl;
return 0;
}