Codeforces 789D

发表于 |

题目

给N个点M条边的图，可能有自环，没有重边。问：有多少条路径能恰好经过M−2条边2次，并且经过其余2条边1次。路径的不同定义为：路径中的边集不同。

数据范围

$0\leq N,M\leq 10^6$

做法

将M条边恰好经过2次可以转化为：将每条边变成2条边，这2M条边恰好经过一次，即走一个欧拉路。由于不存在度数为奇数的点，故欧拉路必存在。

原问题可以规约为：从上文的图中删去2条边，有多少种删法使得剩下的图中仍存在欧拉路。

欧拉路存在的等价条件为：没有孤立的边并且有0个或2个度数为奇数的点。

所以，若原图中没有孤立的边，那么有3种删法：(1)删去2个自环。(2)删去1个自环和一条普通边。(3)删去2个有公共顶点的边。若原图中有孤立的边，则不存在这种路径。

代码

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
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1000005;
int N, M;
vector<int> G[MAX_N];
bool vis[MAX_N], hasLoop[MAX_N];
int selfLoopNum, deg[MAX_N], edgeNum, hasLoopNodeNum;
inline void add_edge(int s, int t)
{
    G[s].push_back(t);
}
void bfs(int s)
{
    queue<int> que;
    que.push(s);
    vis[s] = 1;
    if (hasLoop[s]) hasLoopNodeNum++;
    while (!que.empty()) {
        int v = que.front(); que.pop();
        edgeNum += (int)G[v].size();
        for (int i = 0; i < (int)G[v].size(); ++i) {
            int u = G[v][i];
            if (!vis[u]) {
                if (hasLoop[u]) hasLoopNodeNum++;
                que.push(u);
                vis[u] = 1;
            }
        }
    }
}
bool connected(int s)
{
    bfs(s);
    return edgeNum / 2 + hasLoopNodeNum == M;
}
int main()
{
    scanf("%d%d", &N, &M);
    int bfsStart;
    for (int i = 0; i < M; ++i) {
        int a, b; scanf("%d%d", &a, &b); --a; --b;
        if (a != b) {
            deg[a]++; deg[b]++;
            add_edge(a, b);
            add_edge(b, a);
            bfsStart = a;
        }
        else {
            hasLoop[a] = 1;
            selfLoopNum++;
        }
    }
    if (!connected(bfsStart)) {
        puts("0");
    }
    else {
        ll ans = (ll)selfLoopNum * (selfLoopNum - 1) / 2;
        ans += (ll)selfLoopNum * (M - selfLoopNum);
        for (int i = 0; i < N; ++i) {
            ans += (ll)deg[i] * (deg[i] - 1) / 2;
        }
        printf("%lld\n", ans);
    }
    return 0;
}