题面
给定一个简单无向图，求至少要加多少条边才能使图中包含至少一个简单奇环，求加边的方案数。
$ n,m \leq 10^5 $
Translated by @高飞@Luogu
输入格式
第一行 $n,m$，表示点、边的个数。
接下来 $m$ 行，每行两个整数 $a,b$，表示 $a$ 与 $b$ 之间有一条无向边。
输出格式
一行两个整数，表示最少加边的个数、加边的方案数。
题解
首先分析样例。
Input #1
4 4
1 2
1 3
4 2
4 3
Output #1
1 2
分析 #1
只需要添加紫色边或蓝色边即可构成奇环。
Input #2
3 3
1 2
2 3
3 1
Output #2
0 1
分析 #2
已经成奇环。
Input #3
3 0
Output #3
3 1
分析 #3
自己连个大小为 $3$ 的环出来即可，可以发现任意图中我们都可以用这个方法造出一个环，也就是需要增加的边数一定不会超过 $3$。
那么，答案只可能是 $0,1,2,3$。
我们来逐个解决。
加边数 = 0
直接判断图中是否已有奇环即可，我们用二分图染色的方法来求。
对于每一个联通块进行搜索，交替的进行黑白染色，如果发现已经染过色了，且将要染的色和原色冲突，即一定有奇环，输出 0 1 即可。
加边数 = 1
可以发现，如果一个联通块中有一条长度 $\geq 3$ 且为奇数的路径，即可直接连首尾，形成一个环。
那么如何求方案数呢？还是用染色。任意选两个相同颜色的连一下边都是一种合法方案。
统计联通块 $i$ 中染出的黑、白个数 $cnt[i][0], cnt[i][1]$
则方案数可表示为 $\sum_{i=1}^{totblk}({cnt[i][0]\choose 2}+{cnt[i][1]\choose 2})$
加边数 = 2
这个情况下，每个联通块的大小都只为 $1$ 或 $2$，且必定有一个为 $2$ 的联通块。
只需要从大小为 $2$ 的联通块连两条边到任意其他点上即可。
如图，考虑 ${4,5}$ 这个联通块，向任意其他点连两条边都可以组成一个奇环。
加边数 = 3
这种情况下，显然 $m=0$。
方案数即为 $n\choose 3$
实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
int to,nxt;
}ed[100010*2];int edcnt=0;
int hd[100010];
inline void adde(int u,int v){
ed[++edcnt].to=v;
ed[edcnt].nxt=hd[u];
hd[u]=edcnt;
}
int blk[100010],vis[100010],col[100010],cnt[100010][2];
int n,m;
int nice;
void dfs(int blkid,int u,int fa,int dep){
blk[u]=blkid;
if(vis[u]){
if(col[u]!=!col[fa])
nice++; //奇环标记
return;
}
vis[u]=1;
col[u]=!col[fa];
cnt[blkid][col[u]]++;
for(int id=hd[u];id;id=ed[id].nxt){
int v=ed[id].to;
if(v==fa)continue;
dfs(blkid,v,u,dep+1);
}
}
int totblk=0; //联通块数目
ll ans=0;
inline ll C3(ll x){
return x*(x-1)*(x-2)/2/3;
}
inline ll C2(ll x){
return x*(x-1)/2;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
// 加边数=3
if(m==0){
printf("3 %lld",C3(n));
return 0;
}
int oneok=0; // 标记花费为1是否可能
for(int i=1;i<=n;++i){
if(blk[i])continue;
dfs(++totblk,i,i,0);
if(cnt[totblk][0]>=2 || cnt[totblk][1]>=2) oneok=1;
if(nice){ // 奇环直接输出
puts("0 1");
return 0;
}
}
ll ans=0;
// 加边数=1
if(oneok){
for(int i=1;i<=totblk;++i){
if(cnt[i][0]>=2) ans+=C2(cnt[i][0]);
if(cnt[i][1]>=2) ans+=C2(cnt[i][1]);
}
printf("1 %lld",ans);
return 0;
}
// 加边数=2
ll tot=0;
for(int i=1;i<=totblk;++i){
cnt[i][0]+=cnt[i][1]; // 无需考虑颜色，为方便加到一起
tot+=cnt[i][0];
}
for(int i=1;i<=totblk;++i){
if(cnt[i][0]==2){
ans+=tot-cnt[i][0];
}
}
printf("2 %lld",ans);
}