CF557D Vitaly and Cycle 题解

· · 题解

前置

第一次独立做出来 *2000 的题，肯定是 cf 评分评高了。

题意简述

给定一个 n 个点 m 条边的无向图，问最少添加几条边使图中有奇环，且添加边的方案有多少种。

解题思路

不难发现最多加 3 条边。因为保证 n\geq 3，所以你可以随机选 3 个点然后在它们之间加边，就有奇环了。

具体地说，我们分以下几种情况：

  1. m=0

这时候必须加 3 条边，加边的方案数为 \frac{n\times (n-1)\times (n-2)}{6}。实质就是从 n 个点中选三个点的方案数。

  1. 存在奇环

此时答案为 0 1。主要讲一下如何判断奇环。我们给 dfs 一个参数 len，走到一个点时把这个点的 num 值设成 len，下次再走到时我们判断是否走了奇数步即可（不理解的可以看看代码）。

  1. 存在一个连通块包含至少三个点

这个时候我们只需要连 1 条边。具体的，从连通块中找出距离为偶数且不相邻的点连边即可。注意这个时候我们连的边一定是在块内连，不可能将两个连通块连起来，因为将两个本不相连的连通块连起来不会产生环。

如何统计连边方案数？我们从连通块中任意一个点出发，对整个块黑白染色，连的这一条边要么是黑点和黑点，要么是白点和白点，直接 dfs 统计黑点白点数量然后计算即可。

  1. 其余情况

这个时候我们需要连 2 条边，方案数为 m \times (n-2)。事实上有了前面几种情况铺垫，到这里时，已经保证连通块内点数不超过 2 了。也就是说每一条边都是孤立的！我们假设某条边的两个端点是 x,y，此时我们找到一个 z，从 x,y 分别向 z 连一条边即可。共 m 条边，对于每条边我们可以找到 n-2 个上述的 z 点，所以方案数就出来了。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,vis[200010],cnt_0=0,cnt_1=0,ans=0,num[200010],flg=0;
vector<int> G[200010];
void dfs(int x,int len){
    if(vis[x]){
        if(len-num[x]>=3&&(len-num[x])%2){
            cout<<"0 1"<<endl;
            exit(0);
        }
        return;
    }
    vis[x]=1,num[x]=len;
    if(num[x]%2) cnt_1++;
    else cnt_0++;
    for(int v:G[x]) dfs(v,len+1);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(m==0) return cout<<"3 "<<n*(n-1)*(n-2)/6<<endl,0;
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt_0=cnt_1=0;
            dfs(i,0);
            if(cnt_0>1||cnt_1>1) flg=1;
            ans=ans+cnt_0*(cnt_0-1)/2;
            ans=ans+cnt_1*(cnt_1-1)/2;
        }
    }
    if(flg) cout<<"1 "<<ans<<endl;
    else cout<<"2 "<<m*(n-2)<<endl;
    return 0;
}