我的做法是乱搞，跟std完全不一样 首先如果两个点之间没有边，那么这两个点肯定属于不同的点集 可以 b f s bfs bfs处理肯定属于同一点集的点 然后处理出一些点集，整体思想点集之间如果可以合并成同一个点集就连一条边 跑暴力 d f s dfs dfs求得答案
Code：
#include <bits/stdc++.h> #define maxn 710 using namespace std; int n, m, flag[maxn][maxn], Flag[maxn][maxn], num, color[maxn], type[maxn]; int cnt[maxn][2], a[maxn][2][maxn], can[maxn][2][maxn][2], ans; queue <int> q; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } bool check(int x, int p, int y, int q){ for (int i = 1; i <= cnt[x][p]; ++i) for (int j = 1; j <= cnt[y][q]; ++j) if (Flag[a[x][p][i]][a[y][q][j]]) return 0; return 1; } void dfs(int t, int sum1, int sum2){ if (t > num) ans = min(ans, sum1 * (sum1 - 1) / 2 + sum2 * (sum2 - 1) / 2); else{ if (can[t - 1][0][t][0] && can[t - 1][1][t][1]) dfs(t + 1, sum1 + cnt[t][0], sum2 + cnt[t][1]); if (can[t - 1][0][t][1] && can[t - 1][1][t][0]) dfs(t + 1, sum2 + cnt[t][0], sum1 + cnt[t][1]); } } int main(){ freopen("request.in", "r", stdin); freopen("request.out", "w", stdout); n = read(), m = read(); for (int i = 1; i <= m; ++i){ int x = read(), y = read(); flag[x][y] = flag[y][x] = 1; } for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (i != j && !flag[i][j]) Flag[i][j] = Flag[j][i] = 1; for (int i = 1; i <= n; ++i) if (!color[i]){ color[i] = ++num, type[i] = 1; q.push(i); while (!q.empty()){ int u = q.front(); q.pop(); for (int j = 1; j <= n; ++j) if (Flag[u][j] && !color[j]){ color[j] = num, type[j] = type[u] ^ 1; q.push(j); } } } for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (i != j && color[i] == color[j] && type[i] == type[j] && Flag[i][j]) return puts("-1"), 0; for (int i = 1; i <= num; ++i){ for (int j = 1; j <= n; ++j) if (color[j] == i && type[j]) a[i][1][++cnt[i][1]] = j; else if (color[j] == i && !type[j]) a[i][0][++cnt[i][0]] = j; } for (int i = 1; i < num; ++i) for (int j = 0; j <= 1; ++j) for (int k = 0; k <= 1; ++k) if (check(i, j, i + 1, k)) can[i][j][i + 1][k] = 1; ans = 1e9; dfs(2, cnt[1][0], cnt[1][1]); printf("%d\n", ans); return 0; }