LeetCode 685. 冗余连接 II
原题链接
困难
class Solution {
public:
int n;
vector<bool> st1, st2, st, in_k, in_c;
vector<vector<int>> g;
stack<int> stk;
bool dfs(int u) {
st[u] = true;
stk.push(u), in_k[u] = true;
for(int x : g[u]) {
if(!st[x]) {
if(dfs(x)) return true;
} else if(in_k[x]) {
while(stk.top() != x) {
in_c[stk.top()] = true;
stk.pop();
}
in_c[x] = true;
return true;
}
}
stk.pop(), in_k[u] = false;
return false;
}
void work1(vector<vector<int>>& edges) {
for(auto& e: edges) {
int a = e[0], b = e[1];
g[a].push_back(b);
}
for(int i = 1; i <= n; i ++) {
if(!st[i] && dfs(i)) {
break;
}
}
for(int i = 0; i < n; i ++) {
int a = edges[i][0], b = edges[i][1];
if(in_c[a] && in_c[b]) {
st1[i] = true;
}
}
}
void work2(vector<vector<int>>& edges) {
vector<int> p(n + 1, -1);
for(int i = 0; i < n; i ++) {
int a = edges[i][0], b = edges[i][1];
if(p[b] != -1) {
st2[p[b]] = st2[i] = true;
break;
} else p[b] = i;
}
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
n = edges.size();
st1 = st2 = st = in_k = in_c = vector<bool>(n + 1);
g.resize(n + 1);
work1(edges);
work2(edges);
for(int i = n - 1; i >= 0 ; i --) {
if(st1[i] && st2[i]) {
return edges[i];
}
}
for(int i = n - 1; i >= 0; i --) {
if(st1[i] || st2[i]) return edges[i];
}
return {};
}
};