NOIP2018模拟赛 星际旅行 2018 10 14 T1

题意：

算法：图论（欧拉图）    如果客官想多了解了解，戳->这里<-

难度：NOIP

题解：分三类讨论即可！

1. 两个环
2. 一个环，一条链
3. 两条具有相同节点的链

注意一些细节！！！

代码如下：

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
#define ll long long
using namespace std;
int tot[N],fa[N],deg[N];
int cir,cc[N],vis[N];
int findf(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=findf(fa[x]);
}
int main()
{
	freopen("tour.in","r",stdin);
	freopen("tour.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++)
	{
		fa[i]=i;
	}
	for(int i = 1;i <= m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(a==b)
		{
			deg[a]++;
			cc[++cir]=a;
		}else
		{
			deg[a]++,deg[b]++;
		}
		int t1=findf(a),t2=findf(b);
		if(t1!=t2) fa[t1]=t2;
		vis[a]=1,vis[b]=1;
	}
	int ctt=0;
	for(int i = 1;i <= n;i++)
	{
		if(!vis[i]) continue;
		if(findf(i)==i) ctt++;
		if(ctt>1)
		{
			printf("%d",0);
			return 0;
		}
	}
	ll ans=0;
	for(int i = 1;i <= n;i++)
	{
		ans+=1ll*deg[i]*(deg[i]-1)/2;
	}
	for(int i=1;i<=cir;i++)
	{
		ans+=(ll)m-1ll*deg[cc[i]]-1ll*cir+(ll)1;
	}
	ans+=1ll*cir*(cir-1)/2;
	printf("%I64d",ans);
	return 0 ;
} 
/*
5 4 
1 2
1 3
1 4
1 5
*/