redundant-connection

/*
Runtime: 4 ms, faster than 98.67% of C++ online submissions for Redundant Connection.
Memory Usage: 10.3 MB, less than 47.06% of C++ online submissions for Redundant Connection.
*/

class Solution {
  const static int SIZE = 1001;
  vector<int> gp[SIZE];
  bool usd[SIZE] = {};
  int qq[SIZE] = {};
  int first = 0;
  bool use = true;
public:
    bool dfs(int v, int p=-1) {
      if(usd[v]) {
        first = v;
        return false;
      }
      usd[v] = true;
      bool ok = true;
      for(auto &e : gp[v]) {
        if(e == p) {
          continue;
        }
        if(ok) {
          ok &= dfs(e, v);
        }
      }
      if(!ok && use) {
        qq[v] = 1;
        use = v!=first;
      }
      return ok;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
      int x = 0, len = edges.size();
      for(int i = 0; i < len; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        gp[a].push_back(b);
        gp[b].push_back(a);
        x = b;
      }
      dfs(x);
      for(int i = 0; i < len; i++) {
        if(qq[edges[len-i-1][0]]+qq[edges[len-i-1][1]] == 2) {
          return edges[len-i-1];
        }
      }
      return edges[0];
    }
};