Problem Description: https://arc099.contest.atcoder.jp/tasks/arc099_c
This problem is one that requires thoughts on complement graph. The official editorial has done a pretty good job in explanation.
Step: Convert into complement graph -> Find characteristic of this graph -> Bipartite graph -> Convert back -> Find minimum roads -> DP
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> #include <stack> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1005; int N,M; bool conn[maxn][maxn]; int col[maxn],cnt[maxn],f[maxn][maxn]; bool dfs(int u,int c){ cnt[c]++; col[u] = c; for(int i = 1; i <= N; i++){ if(!conn[u][i]){ if(!col[i]){ if(!dfs(i,3 - c)) return 0; } else if(col[i] == c) return 0; } } return 1; } int main(){ FAST_IO cin>>N>>M; for(int i = 1; i <= M; i++){ int a,b; cin>>a>>b; conn[a][b] = conn[b][a] = 1; } for(int i = 1; i <= N; i++) conn[i][i] = 1; f[0][0] = 1; int now = 0; for(int i = 1; i <= N; i++){ if(!col[i]){ now++; cnt[1] = cnt[2] = 0; if(!dfs(i,1)){ cout<<-1<<endl; return 0; } for(int j = 0; j <= N; j++) if(f[now - 1][j]) f[now][j + cnt[1]] = f[now][j + cnt[2]] = 1; } } int ans = INT_MAX; for(int i = 0; i <= N; i++){ if(f[now][i]){ ans = min(ans, i * (i - 1) / 2 + (N - i) * (N - i - 1) / 2); } } cout<<ans<<endl; return 0; }