USACO Wormholes Solution

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

struct Point {
    int x;
    int y;
};

class Wormholes {
    private:
        const vector<Point>& wormholes;
        vector<int> to_the_right;
        vector<int> partners;
    public:
        Wormholes(const vector<Point>& wormholes)
                : wormholes(wormholes),
                  to_the_right(wormholes.size(), -1),
                  partners(wormholes.size(), -1) {
            for (int w = 0; w < wormholes.size(); w++) {
                vector<int> poss_next;
                for (int ow = 0; ow < wormholes.size(); ow++) {
                    if (wormholes[w].y == wormholes[ow].y
                            && wormholes[w].x < wormholes[ow].x) {
                        poss_next.push_back(ow);
                    }
                }
                std::sort(
                    poss_next.begin(), poss_next.end(), [&] (int w1, int w2) {
                    return wormholes[w1].x < wormholes[w2].x;
                });
                if (!poss_next.empty()) {
                    to_the_right[w] = poss_next.front();
                }
            }
        }

        int count_valid() {
            // cout << partners << endl;
            bool all_paired = true;
            int w = 0;
            for (; w < wormholes.size(); w++) {
                if (partners[w] == -1) {
                    all_paired = false;
                    break;
                }
            }
            if (all_paired) {
                return inf_loop_possible();
            }

            int total = 0;
            for (int ow = w + 1; ow < wormholes.size(); ow++) {
                if (partners[ow] == -1) {
                    partners[w] = ow;
                    partners[ow] = w;
                    total += count_valid();
                    partners[w] = partners[ow] = -1;
                }
            }
            return total;
        }

        bool inf_loop_possible() {
            for (int s = 0; s < wormholes.size(); s++) {
                int pos = s;
                for (int i = 0; i < wormholes.size(); i++) {
                    if (to_the_right[pos] == -1) {
                        break;
                    }
                    pos = partners[to_the_right[pos]];
                    if (pos == s) {
                        return true;
                    }
                }
            }
            return false;
        }
};

int main() {
    std::ifstream read("wormhole.in");

    int wormhole_num;
    read >> wormhole_num;
    vector<Point> wormholes(wormhole_num);
    for (Point& p : wormholes) {
        read >> p.x >> p.y;
    }

    std::ofstream("wormhole.out") << Wormholes(wormholes).count_valid() << endl;
}