思路

题目挺简单的，但是要 认 真 看 题！！！

今天一看题，第一想法，把调用k的方法断掉，并查集秒了。

写完之后把案例放上去一看，天塌了，题目要求

*方法 k 以及它直接或间接调用的任何方法都被视为 可疑方法*

我给想成

*方法 k 以及直接或间接调用它的任何方法都被视为 可疑方法*

之后一直在并查集上修修补补发现好像不行。

重新梳理后改用BFS。先把可疑方法染色，然后检查是否有方法调用被染色的方法，如果没有输出没被染色的方法，否则输出所有方法。

代码```
class Solution {
public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
List<Integer>[] path = new List[n];
for (int i = 0; i < n; i++) {
path[i] = new ArrayList<>();
}
for (int[] invocation : invocations) {
path[invocation[0]].add(invocation[1]);
}
boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<>();
queue.add(k);
while (!queue.isEmpty()) {
int cur = queue.poll();
visited[cur] = true;
for (int next : path[cur]) {
if (!visited[next]) {
queue.add(next);
}
}
}
boolean canRemove = true;
for (int[] invocation : invocations) {
if (!visited[invocation[0]] && visited[invocation[1]]) {
canRemove = false;
break;
}
}
List<Integer> ans = new ArrayList<>();
if (canRemove) {
for (int i = 0; i < n; i++) {
if (!visited[i]) {
ans.add(i);
}
}
} else {
for (int i = 0; i < n; i++) {
ans.add(i);
}
}
return ans;
}
}

算术评级 5 第 418 场周赛 Q2 难度分 1711

写了一坨效率很低的方法```
class Node:
def __init__(self, val):
self.val=val
self.children=[]
self.indegrees=0
self.outdegrees=0

def add(self, next):
self.children.append(next)

class Solution:
def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
node_dict = defaultdict()
for a, b in invocations:
if a not in node_dict:
a_node=Node(a)
node_dict[a]=a_node
if b not in node_dict:
b_node=Node(b)
node_dict[b]=b_node
a_node=node_dict[a]
b_node=node_dict[b]
a_node.add(b)
a_node.outdegrees+=1
b_node.indegrees+=1
visited=[False]*n
def dfs(i):
if visited[i]: return
visited[i]=True
node_i = node_dict[i]
for j in node_i.children:
dfs(j)
total_indegrees=total_outdegrees=0
if k in node_dict:
dfs(k)
for i in range(n):
if visited[i]:
total_indegrees+=node_dict[i].indegrees
total_outdegrees+=node_dict[i].outdegrees
else:
visited[k]=True
if total_indegrees==total_outdegrees:
return [i for i in range(n) if not visited[i]]
else:
return list(range(n))

看懂题目就是bfs/dfs就好。```
class Solution {
public:
vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
vector<bool> st(n,false);
vector<vector<int>> g(n,vector<int>());
for(const auto& e : invocations) {
int u = e[0], v = e[1];
g[u].push_back(v);
}
queue<int> q;
q.push(k);
st[k] = true;
while(q.size()) {
auto u = q.front();
q.pop();
for(const auto& v : g[u]) {
if(!st[v]) {
st[v] = true;
q.push(v);
}
}
}
bool ok = true;
for(int i = 0; i < n && ok; i++) {
if(!st[i]) {
for(const auto& j : g[i]) {
if(st[j]) {
ok = false;
break;
}
}
}
}
vector<int> res;
for(int i = 0; i < n; i++) {
if(ok && st[i]) continue;
res.push_back(i);
}
return res;
}
};

这题目是给人类看的吗 ^-^```
impl Solution {
pub fn remaining_methods(n: i32, k: i32, invocations: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let k = k as usize;
let mut edge: Vec<Vec<usize>> = vec![vec![]; n];
let mut sus: Vec<bool> = vec![false; n];
for invocation in invocations.iter() {
let (a, b) = (invocation[0] as usize, invocation[1] as usize);
edge[a].push(b);
}
fn f(sus: &mut Vec<bool>, edge: &Vec<Vec<usize>>, i: usize) {
if sus[i] { return; }
sus[i] = true;
for &e in edge[i].iter() {
f(sus, edge, e);
}
}
```

不知道为啥发不出去, 老是提示Awaiting Approval, 用图片似乎可以 ^-^

感觉这题主要难点是在于阅读理解。。。```
class Solution:
def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
g = [[] for _ in range(n)]
for u, v in invocations:
g[u].append(v)

vis = [0] * n
def dfs(u):
vis[u] = 1
for v in g[u]:
if not vis[v]:
dfs(v)

dfs(k)
# 无法移除 所有 可疑方法，则 不 移除任何方法
for u, v in invocations:
if not vis[u] and vis[v]:
return list(range(n))

ans = []
for i in range(n):
if not vis[i]:
ans.append(i)
return ans