ATC MUJIN C. Orange Graph ( Bipartite + Union Find )

C: オレンジグラフ / Orange Graph - MUJIN プログラミングチャレンジ Programming Challenge | AtCoder
It is already a well known fact that not to include any odd cycle is equivalent to having the graph bipartite. Since N is small ( ≤ 16 ), we can enumerate all subsets of vertices, splitting them bipartitely, and unite vertices having edge that are of different color. In this way, if all vertices are united together, it is maximized. However, if there are some vertices not united, it is not maximized because there exist some isolated vertices that are assigned bad colors though it will not form odd cycle if any edge connects with them.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 16 + 2;
const int MAXM = MAXN * MAXN / 2;

struct UnionFind{
    int fa[ MAXN ];
    void init(int n){
        for(int i = 0; i <= n; ++i)
            fa[ i ] = i;
    }
    int find(int x){
        return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
    }
    bool unite(int a, int b){
        int x = find( a ), y = find( b );
        if( x == y ) return false;
        fa[ x ] = y; return true;
    }
} uf;

int n, m;
pii es[ MAXM ];

void solve(){
    set< vector<int> > edge_set;
    for(int S = 0; S < ( 1 << n ); ++S){
        uf.init( n );
        vector<int> took_edge;
        for(int i = 0; i < m; ++i){
            int u = es[ i ].first, v = es[ i ].second;
            if( ( ( S >> u ) & 1 ) != ( ( S >> v ) & 1 ) ){
                took_edge.push_back( i );
                uf.unite( u, v );
            }
        }
        bool maximized = true;
        for(int i = 1; i < n; ++i)
            if( uf.unite( 0, i ) )
                maximized = false;
        if( !maximized ) continue;
        edge_set.insert( took_edge );
    }
    printf("%d\n", edge_set.size());
    /*for(set< vector<int> >::iterator it = edge_set.begin(); it != edge_set.end(); ++it, puts(""))
        for(int i = 0; i < it->size(); ++i)
            printf("%d ", (*it)[i]); */
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i){
        int a, b; scanf("%d%d", &a, &b);
        es[ i ] = pii( --a, --b );
    }
    solve();
    return 0;
}