TCO Round2 Med MakingRegularGraph

MakingRegularGraph.cpp

struct MakingRegularGraph {
  int n;
  vector<int> x, y, deg;
  set<int> rest;
  set<pair<int, int>> edge;

  void dfs(vector<int> &ans) {
    if (rest.size() == 0) {
      return ;
    } else if (rest.size() == 1) {
      ans.emplace_back(-1);
      return ;
    }
    int x = *rest.begin();
    set<int> tmp = rest;
    for (int y : tmp) {
      if (x != y and edge.find(make_pair(x, y)) == edge.end()) {
        edge.emplace(x, y);
        deg[x]++, deg[y]++;
        ans.emplace_back(x);
        ans.emplace_back(y);
        if (deg[x] == 2) rest.erase(x);
        if (deg[y] == 2) rest.erase(y);
        dfs(ans);
        if (ans.back() != -1) return ;

        REP(_, 3) ans.pop_back();
        deg[x]--, deg[y]--;
        edge.erase(make_pair(x, y));
        rest.emplace(x);
        rest.emplace(y);
      }
    }
    ans.emplace_back(-1);
  }

  vector<int> addEdges(int _n, vector<int> _x, vector<int> _y) {
    n = _n, x = _x, y = _y;
    deg.assign(n, 0);
    edge.clear(), rest.clear();
    for (int i = 0; i < (int)x.size(); i++) {
      deg[x[i]]++, deg[y[i]]++;
      edge.emplace(x[i], y[i]);
    }

    for (int i = 0; i < n; i++) {
      if (deg[i] <= 1) rest.emplace(i);
    }

    vector<int> ans;
    dfs(ans);
    return ans;
  }
};