【C++图论 BFS】3310. 移除可疑的方法|1710

闻缺陷则喜何志丹

2195人浏览 · 2024-12-02 07:00:00

闻缺陷则喜何志丹 · 2024-12-02 07:00:00 发布

本文涉及知识点

LeetCode3310. 移除可疑的方法

你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1。
给你两个整数 n 和 k，以及一个二维整数数组 invocations，其中 invocations[i] = [ai, bi] 表示方法 ai 调用了方法 bi。
已知如果方法 k 存在一个已知的 bug。那么方法 k 以及它直接或间接调用的任何方法都被视为可疑方法，我们需要从项目中移除这些方法。
只有当一组方法没有被这组之外的任何方法调用时，这组方法才能被移除。
返回一个数组，包含移除所有可疑方法后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除所有可疑方法，则不移除任何方法。
示例 1:
在这里插入图片描述

输入: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]
输出: [0,1,2,3]
解释:

方法 2 和方法 1 是可疑方法，但它们分别直接被方法 3 和方法 0 调用。由于方法 3 和方法 0 不是可疑方法，我们无法移除任何方法，故返回所有方法。
示例 2:
在这里插入图片描述

输入: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]]
输出: [3,4]
解释:
方法 0、方法 1 和方法 2 是可疑方法，且没有被任何其他方法直接调用。我们可以移除它们。
示例 3:
在这里插入图片描述

输入: n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]]
输出: []
解释:
所有方法都是可疑方法。我们可以移除它们。
提示:
1 <= n <= 10⁵
0 <= k <= n - 1
0 <= invocations.length <= 2 * 10⁵
invocations[i] == [ai, bi]
0 <= ai, bi <= n - 1
ai != bi
invocations[i] != invocations[j]

BFS

由于有环，用BFS获取可疑方法更方便。
枚举所有非可疑方法，如果有非可疑方法指向可疑方案，则返回所有方法；否则，返回非可疑方法。

代码

核心代码

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

class Solution {
		public:
			vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
				auto neiBo = CNeiBo::Two(n, invocations, true);
				vector<bool> vis(n);
				queue<int> que;
				auto Add = [&](int cur) {
					if (vis[cur]) { return; }
					vis[cur] = true;
					que.emplace(cur);
				};
				Add(k);
				while (que.size()) {
					const auto cur = que.front();
					que.pop();
					for (const auto& next : neiBo[cur]) {
						Add(next);
					}
				}
				bool bCal = false;
				for (const auto& e : invocations) {
					if (!vis[e[0]] && vis[e[1]]) { bCal =true; }
				}
				if (bCal) {
					vector<int> ans(n);
					iota(ans.begin(), ans.end(), 0);
					return ans;
				}
				vector<int> ans;
				for (int i = 0; i < n; i++) {
					if (!vis[i]) { ans.emplace_back(i); }
				}
				return ans;
			}
		};

单元测试

int n,  k;
		vector<vector<int>> invocations;
		TEST_METHOD(TestMethod1)
		{
			n = 4, k = 1, invocations = { {1,2},{0,1},{3,2} };
			auto res = Solution().remainingMethods(n, k, invocations);
			AssertEx({ 0,1,2,3 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			n = 5, k = 0, invocations = { {1,2},{0,2},{0,1},{3,4} };
			auto res = Solution().remainingMethods(n, k, invocations);
			AssertEx({ 3,4}, res);
		}
		TEST_METHOD(TestMethod3)
		{
			n = 3, k = 2, invocations = { {1,2},{0,1},{2,0} };
			auto res = Solution().remainingMethods(n, k, invocations);
			AssertEx({  }, res);
		}
		TEST_METHOD(TestMethod4)
		{
			n = 3, k = 2, invocations = { {1,0},{2,0} };
			auto res = Solution().remainingMethods(n, k, invocations);
			AssertEx({ 0,1,2 }, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功