题目链接：
题意：给你n个点，m条边，，问你最少加几条边，使得有奇环（环的边数为奇数）存在，并输出共有几种方法。
思路：这题我们可以用二分图来做，添加边的情况有四种：
①0条边，那么肯定至少要添加三条边，方法数就是n*(n-1)*(n-2) / 6；
②每个点至多连一条边，那么肯定要添加三条边，方法数就是m*(n-2))；
③给二分图染色，即分成 X 和 Y 集合，若有点被染两次，意味着不能构成二分图，那么就不需要添加任何边，它本身就有奇环，输出 0 1 就好了；
④可以构成二分图，且线有交叉，那么只需添一条边就够了，给连通的点做标记，再讲X集合和Y集合的分开算，最后两个方法数相加即可。
代码如下：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<vector> #include<queue>using namespace std;const int N = 1e5+10;typedef long long ll;int n, m, top;vector<int> G[N];int col[N], num[N], siz[N];bool bfs(int u)//二分图染色 {col[u] = 1;queue<int>q;q.push(u);while(!q.empty()){u = q.front(); q.pop();for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(col[v]){if(col[v] == col[u])return false;}else{col[v] = 3 – col[u];q.push(v);}}}return true;}void paint(int u){top++;queue<int>q;q.push(u);siz[u] = top;while(!q.empty()){u = q.front(); q.pop();for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(siz[v] == 0){siz[v] = top;q.push(v);}}} }ll work(int color){memset(num, 0, sizeof(num));for(int i = 1; i <= n ; i++){if(col[i] == color)num[siz[i]]++;} ll ans = 0;for(int i = 1; i <= top; i++){ans += (ll)num[i]*(num[i]-1)/2;}return ans;}void cal(){for(int i = 1; i <= n; i++){if(col[i] == 0){if(bfs(i) == false){printf("0 1\n"); return ;}}}top = 0;for(int i = 1; i <= n ; i++){if(siz[i] == 0) paint(i);}printf("1 ");printf("%I64d\n", work(1) + work(2));}int main(){int s, d;scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++){scanf("%d%d", &s, &d);G[s].push_back(d);G[d].push_back(s);}if(m == 0){printf("3 ");printf("%I64d\n", (ll)n*(n-1)*(n-2) / 6);return 0;} bool two = false;for(int i = 1 ; i <= n; i++){if(G[i].size() >= 2) two = true;}if(two == false){printf("2 ");printf("%I64d\n", (ll)m*(n-2));return 0;}memset(col, 0, sizeof(col));cal();}
版权声明：本文为博主原创文章，未经博主允许不得转载。
因害怕失败而不敢放手一搏，永远不会成功
