leetcode 困难题 1601. 最多可达成的换楼请求数目

Problem: 1601. 最多可达成的换楼请求数目不申请调换的直接累加得到ret然后得到邻接表数组tr存储了边的索引i和终点c {c, i}拿到可能存在环的起点集合te和数组arr起点和终点相同第一个回溯dfs函数从环的起点开始求出所有可能的环存放在数组circle内然后删除重复的环circleCOPY第二次回溯recursion函数选取可能的环若环之间不存在并集则合并这两个环最后求出最大值ansCodeclass Solution { public: vectorvectorpairint, int tr; vectorvectorint circle, circleCOPY; vectorint temp; vectorbool sta; int ans 0, flag; void dfs(int origin, int start, int num) { int next, index; for(pairint, int tmp : tr[start]) { next tmp.first; index tmp.second; if(sta[index] false) { sta[index] true; temp.push_back(index); if(next origin) { circle.push_back(temp); } dfs(origin, next, num 1); sta[index] false; temp.pop_back(); } } } unordered_setint tes, copy; void recursion(int index) { if(index (int)circle.size()) { ans max((int)tes.size(), ans); return; } bool join false; int a; for(int i 0; i circle[index].size(); i) { a circle[index][i]; if(tes.find(a) ! tes.end()) { join true; break; } } if(join false) { copy tes; for(int i 0; i circle[index].size(); i) { a circle[index][i]; tes.insert(a); } recursion(index 1); tes copy; } recursion(index 1); } int maximumRequests(int n, vectorvectorint requests) { int m requests.size(), a, c, ret 0; setint te; tr.resize(n); sta.assign(m, false); for(int i 0; i m; i) { a requests[i][0]; c requests[i][1]; if(a c) ret; else tr[a].push_back({c, i}); for(int j i 1; j m; j) { if(a requests[j][1]) { te.insert(a); break; } } } vectorint arr; for(const int i : te) arr.push_back(i); for(int i : arr) { dfs(i, i, 0); } for(int i 0; i circle.size(); i) { sort(circle[i].begin(), circle[i].end()); } vectorbool dele((int)circle.size(), false); for(int i 0; i circle.size(); i) { if(dele[i]) continue; for(int j i 1; j circle.size(); j) { if(dele[j]) continue; if(circle[i]circle[j]) { dele[j] true; } } } for(int i 0; i circle.size(); i) { if(dele[i] false) { ans max(ans, (int)circle[i].size()); circleCOPY.push_back(circle[i]); } } circle std::move(circleCOPY); temp.clear(); recursion(0); return ans ret; } };