CF788B Weird journey

考虑将所有边视作两条边，那么问题转化为删除两条边后图是一个欧拉图，即只有两个点度数为偶数且图连通。而每条边视作两条边后所有点度数一定都是偶数了，删除一条边一定会使两个点度数同时变为奇数，那么要为欧拉图，删除的两条边一定有一个公共点，或者至少有一个是自环。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        flag |= c == '-';
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1e6 + 10;
bool vis[N];
int n, m, p[N], d[N];
int fa (int x) { return p[x] == x ? x : p[x] = fa(p[x]); }
int main ()
{
    read(n, m);
    for (int i = 1; i <= n; ++i) p[i] = i;
    int t = 0;
    for (int i = 1, a, b; i <= m; ++i)
    {
        read(a, b);
        vis[a] = vis[b] = true;
        if (a == b) ++t;
        else ++d[a], ++d[b], p[fa(a)] = fa(b);
    }
    int tot = 0;
    for (int i = 1; i <= n; ++i)
        tot += vis[i] && p[i] == i;
    if (tot > 1) return puts("0"), 0;
    LL res = (LL)(t - 1) * t / 2 + (LL)t * (m - t);
    for (int i = 1; i <= n; ++i)
        res += (LL)d[i] * (d[i] - 1) / 2;
    write(res);
    return 0;
}