codeforces 788B Weird journey （欧拉路）_codeforces 欧拉路

题目分析

这道题读到题面我想到了欧拉通路，欧拉通路是这样的，如果一个图是连通图，并且对于图上的每个点的度数都是偶数，只有2个点的度数是奇数，那么我们可以选择这2个点分别作起点和终点，这样必然存在欧拉路径。本题要求m-2条路走2遍，还有2条路走一遍，因为每一条无向边对应2条有向边，那么很明显每个点的入度都是偶数，这样的话我们只能够选取具有公共节点的边，这样处理过后才会剩下2个奇度节点，同样对于起点和终点相同的边，我们可以另外找任一一条边与之对应不能走，但是这时候需要去重，因为自环边和自环边计算了2遍，那么在我减去重合的值即可。

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+100;
#define LL long long

vector <int> G[maxn];
int degree[maxn], fa[maxn];

int Find(int x){
    return x == fa[x]?fa[x]:fa[x] = Find(fa[x]);
}

void init(){
    memset(degree, 0, sizeof(degree));
    for(int i = 0; i < maxn; i++){
        fa[i] = i;
        G[i].clear();
    }
}

int main(){
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF){
        init();
        int u, v, tot = 0;
        for(int i = 0; i < m; i++){
            scanf("%d%d", &u, &v);
            degree[u]++, degree[v]++;
            if(u != v){
                G[u].push_back(v);
                G[v].push_back(u);
                int xx = Find(u), yy = Find(v);
                if(xx != yy) fa[xx] = yy;
            }
            else tot++;
        }
        int father = -1;
        for(int i = 1; i <= n; i++)if(G[i].size()){
            father = Find(i);
            break;
        }

        for(int i = 1; i <= n; i++)if(degree[i] && Find(i) != father){
            printf("0\n");
            return 0;
        }
        LL ans = 0;
        for(int i = 1; i <= n; i++){
            ans += (LL)(G[i].size())*(G[i].size()-1)/2;
        }
        ans = ans + (LL)tot*(m-1) - (LL)tot*(tot-1)/2;
        printf("%I64d\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60