星际旅行(思维很好的欧拉路)
把每条边拆成两条。欧拉(回)路,只有0或2两个奇点。因为2条边经过一次,m-2条边经过两次,可以考虑删除两条边,使剩下的图有0或2两个奇点。所以这两条边要么是任意两个自环,要么是有一个公共端点的两条边,要么是一个自环和任意一条边。
我们要判断,整个图联不联通,因为要经过m条边。然而我们判断所有边联通的点联不联通,不是判断所有点联不联通。如下图,所有点不联通,但是能找到航线。
#include<bits/stdc++.h>
using namespace std;
long long fa[1000010], n, m, ru[1000010], zuo[1000010], you[1000010], si;
int find(int x)
{
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void unio(int x,int y)
{
int r1 = find(x); int r2 = find(y); fa[r1] = r2;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= m; i++)
{
scanf("%d%d",&zuo[i],&you[i]);
if(zuo[i]!= you[i]){
unio(zuo[i],you[i]);ru[you[i]]++; ru[zuo[i]]++;
}else si++;
}
int ha = find(zuo[1]);
for(int i = 2; i <= m; i++)
{
int he = find(zuo[i]);
if(ha != he) {
printf("0"); return 0;
}
}
long long ans = 0;
ans = si * (si-1);
ans += si * (m - si);
for(int i = 1; i <= n; i++)
ans += ru[i] * (ru[i] - 1)/2;
cout << ans;
return 0;
}