题目大意：给出一个 n 点 m 边的图，问最少加多少边使其能够存在奇环，加最少边的情况数有多少种。
解题关键：黑白染色求奇环，利用数量分析求解。
奇环：含有奇数个点的环。
二分图不存在奇环。反之亦成立。
#include#include #include #include #include #include using namespace std;typedef long long ll;const int maxn=1e5+5;const int maxm=1e5+5;int c[maxn]; //color，每个点的黑白属性，-1表示还没有标记，0/1表示黑白,比vis数组多一个作用ll num[2]; //在一次DFS中的黑白点个数bool f=0; //判断是否出现奇环int head[maxn],tot,n,m,a,b;struct edge{ int to; int nxt;}e[2*maxm];void add_edge(int u,int v){ e[tot].to=v; e[tot].nxt=head[u]; head[u]=tot++;}void init(){ memset(head,-1,sizeof head); tot=0; memset(c,-1,sizeof c);}void dfs(int u,int x){ if(f)return; c[u]=x; num[x]++; for(int i=head[u];~i;i=e[i].nxt){ int j=e[i].to; if(c[j]==-1) dfs(j,!x); else if(c[j]==x){ //存在奇环 f=1; return; } }}int main(){ init(); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a>>b; add_edge(a,b); add_edge(b,a); } ll ans=0,ans2=0; if(m==0){ ans=(ll)n*(n-1)*(n-2)/6; printf("3 %lld\n",ans); return 0; } for(int i=1;i<=n&&(!f);i++){ if(c[i]==-1){ num[0]=num[1]=0; dfs(i,1); ans+=(num[0]*(num[0]-1)+num[1]*(num[1]-1))/2; if(num[0]==1&&num[1]==1){ ans2+=n-2; } } } if(f) printf("0 1\n"); else if(ans) printf("1 %lld\n",ans); else printf("2 %lld\n",ans2); return 0;}