CF #311 D. Vitaly and Cycle 加最少边形成奇圈

题目链接：http://codeforces.com/problemset/problem/557/D

大意 给出一个未必联通的无向图（点数至少为3），问最少加多少边可以形成一个奇圈，以及这样做的方案有多少种。

首先如果是一张没有边的图，那么直接就是需要加三条边，有C(n,3)种方式。

接着，判断这张图每一个联通块是否是一个二分图，因为二分图是一定没有奇圈的。如果有联通块不是二分图，那么也就是意味着存在奇圈，这样的话需要加0条边，方式为1种。

接下去还需要分两种情况讨论

1.如果所有的联通块都只有1个或者2个点，则至少需要加2条边，方式为所有点数为2的联通块随便选择一个其他的点加2条边，故统计所有点数为2的联通块数量。

2.存在至少包含3个点的联通块，注意，此时已经排除了联通块不是二分图的情况，所以也即联通块一定是二分图。对于二分图，连接x部和y部的边是不会形成奇圈的，这种情况下只需要连接一条相同部之间的边即可。所以方案数为对于所有至少包含3个点的联通块，计算x部和y部点数，对答案累加上 C(cntx,2)+C(cnty,2)

 #include <iostream>
 #include <vector>
 #include <algorithm>
 #include <string>
 #include <string.h>
 #include <stdio.h>
 #include <math.h>
 #include <stdlib.h>
 #include <queue>
 #include <stack>
 #include <map>
 #include <set> using namespace std; const int N=1e5+; vector<int> edge[N];
 bool vis[N];
 int col[N];
 bool found=false;
 int cnt[];
 void dfs(int u,int c) {
     vis[u]=true;
     col[u]=c;
     cnt[c]++;
     for (int i=;i<edge[u].size();i++) {
         int v=edge[u][i];
         if (vis[v]&&col[v]==c) {
             found=true;
         }
         if (vis[v]) continue;
         dfs(v,c^);
     }
 }
 int main(){
     int n,m;
     scanf("%d %d",&n,&m);
     for (int i=;i<=m;i++) {
         int u,v;
         scanf("%d %d",&u,&v);
         edge[u].push_back(v);
         edge[v].push_back(u);
     }
     if (m==) {
         long long ret=1LL*n*(n-)*(n-)/6LL;
         cout<<<<" "<<ret<<endl;
     }
     else {
         found=false;
         bool three=false;
         long long retThree=;
         int cnt2=;
         for (int i=;i<=n&&!found;i++) {
             if (vis[i]) continue;
             cnt[]=cnt[]=;
             dfs(i,);
             if (cnt[]+cnt[]>=){
                 three=true;
                 retThree+=1LL*cnt[]*(cnt[]-)/2LL+1LL*cnt[]*(cnt[]-)/2LL;
             }
             else if (cnt[]+cnt[]==)
                 cnt2++;
         }
         if (found) {
             cout<<<<" "<<<<endl;
         }
         else if (three){
             cout<<<<" "<<retThree<<endl;
         }
         else {
             long long ret=1LL*cnt2*(n-);
             cout<<<<" "<<ret<<endl;
         }
     }
     return ;
 }