AtCoder Regular 099E: Independence

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;
}