USACO-T014: Wormholes

/*
ID: mickyta1
TASK: wormhole
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

#define r first
#define c second
typedef pair<int, int> pii;

const int N = 12 + 5;

enum status {
    UNCHECK, CHECKING, CHECKED
};

map<int, int> cols;
vector<pii> adj[N];
pii coor[N];
int permu[N], con[N], n;
status visited[N];

bool DFSCycle(int u){
    if(visited[u] == CHECKING){
        return true;
    }
    if(visited[u] == CHECKED){
        return false;
    }
    visited[u] = CHECKING;
    int ur = coor[u].r;
    int uc = coor[u].c;
    int i = cols[uc];
    vector<pii>::iterator itr = upper_bound(adj[i].begin(), adj[i].end(), pii(ur, 1e9));
    if(itr != adj[i].end()){
        int v = itr -> second;
        if(DFSCycle(con[v])){
            return true;
        }
    }
    visited[u] = CHECKED;
    return false;
}

int cnt = 0;
void BFCheck(){
    for(int u = 1; u <= n; ++u){
        visited[u] = UNCHECK;
    }
    for(int u = 1; u <= n; ++u){
        if(visited[u] == UNCHECK && DFSCycle(u)){
            ++cnt;
            return;
        }
    }
}

void BFRecur(int i){
    if(i > n){
        BFCheck();
        return;
    }
    for(int j = i + 1; j <= n; ++j){
        swap(permu[i + 1], permu[j]);
        con[permu[i]] = permu[i + 1];
        con[permu[i + 1]] = permu[i];
        BFRecur(i + 2);
        swap(permu[i + 1], permu[j]);
    }
}

int main(){

    freopen("wormhole.in", "r", stdin);
    freopen("wormhole.out", "w", stdout);

    scanf("%d", &n);
    int colCnt = 0;
    for(int i = 1; i <= n; ++i){
        int r, c;
        scanf("%d%d", &r, &c);
        coor[i] = pii(r, c);
        map<int, int>::iterator itr = cols.find(c);
        if(itr == cols.end()){
            cols[c] = ++colCnt;
            adj[colCnt].emplace_back(r, i);
        } else {
            adj[itr -> second].emplace_back(r, i);
        }
    }
    for(int i = 1; i <= colCnt; ++i){
        sort(adj[i].begin(), adj[i].end());
    }
    for(int i = 1; i <= n; ++i){
        permu[i] = i;
    }
    BFRecur(1);
    cout << cnt << '\n';

    fclose(stdin);
    fclose(stdout);

    return 0;
}