「Codeforces 788B」Weird Journey

发表于 | | 阅读次数:
字数统计: 587 字

Description

题目链接：Codeforces 788B

众所周知，Uzhlyandia 有 $n$ 个城市由 $m$ 条道路相连（保证没有重边，但是可能有自环）。定义一条路径是好的，当且仅当这条路径经过 $m-2$ 条边恰好 $2$ 次，另外 $2$ 条边经过恰好 $1$ 次。路径的起始城市和结束城市可以是任意的。

现在请你计算出有多少条路径是好的，两条路径是不同的当且仅当有一条边不同。

数据范围：$1\le n,m\le 10^6$

Solution

路径经过 $2$ 次很难处理，我们把每条路径复制一遍，这样一来得到：其中 $2$ 条边不经过，其余边恰好经过 $1$ 次。

换言之，我们把这张新图上的 $2$ 条边删去，这张图存在欧拉路径（不多于 $2$ 个点的度数为奇数）。

新图中，显然每个点的度数都是偶数了，我们那么有如下 $3$ 种删边方法：

  • 删去两个自环（这个点的度数 $-4$）。
  • 删去一个自环和任意一条普通的边（一个点的度数 $-2$，另外两个点度数各 $-1$）。
  • 删去两条有共同端点的边（一个点度数 $-2$，另外两个点度数各 $-1$）。

统计自环个数、边数、度数即可得到答案。

最后注意一下无解情况！不一定是图不连通，比如 $\text{Codeforces}$ 上的这组数据（应该是有解的）：

1
2
3
4
5
 
4 4
2 3
2 4
3 4
4 4

因此无解当且仅当有连边的点之间相互连通。

时间复杂度：$O(m+n\cdot\alpha(n))$

Code

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
 
#include <cstdio>
#include <algorithm>

const int N=1e6+5;
int n,m,deg[N],fa[N];
bool vis[N];

int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) fa[i]=i;
    int cnt=0;
    for(int i=1;i<=m;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        vis[u]=vis[v]=1;
        if(u==v) ++cnt;
        else ++deg[u],++deg[v];
        fa[find(u)]=find(v);
    }
    int rt=0;
    for(int i=1;i<=n;++i) if(vis[i]) {rt=i;break;}
    for(int i=1;i<=n;++i) if(vis[i]&&find(i)!=find(rt)) return puts("0"),0;
    long long ans=0;
    ans+=1LL*cnt*(m-cnt);
    ans+=1LL*cnt*(cnt-1)/2;
    for(int i=1;i<=n;++i) ans+=1LL*deg[i]*(deg[i]-1)/2;
    printf("%lld\n",ans);
    return 0;
}
0%