【图论】【拓扑排序】1857. 有向图中最大颜色值

本文涉及的知识点

图论拓扑排序

LeetCode1857. 有向图中最大颜色值

给你一个有向图，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。
给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的颜色（下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条有向边。
图中一条有效路径是一个点序列 x1 -> x2 -> x3 -> … -> xk ，对于所有 1 <= i < k ，从 xi 到 xi+1 在图中有一条有向边。路径的颜色值是路径中出现次数最多颜色的节点数目。
请你返回给定图中有效路径里面的最大颜色值。如果图中含有环，请返回 -1 。

示例 1：

在这里插入图片描述

输入：colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 “a” 的节点（上图中的红色节点）。
示例 2：

在这里插入图片描述

输入：colors = “a”, edges = [[0,0]]
输出：-1
解释：从 0 到 0 有一个环。

提示：

n == colors.length
m == edges.length
1 <= n <= 10⁵
0 <= m <= 10⁵
colors 只含有小写英文字母。
0 <= aj, bj < n

拓扑排序

建立后邻接表后，直接调用拓扑排序的封装类。
拓扑排序保证排除已经处理节点后，当前节点的出度为0。也就是当前节点能够到达的节点都已经处理。这保证无后效性。
每个节点。
如果拓扑排序没有处理完所有节点，说明有环。
m_vLen[cur][i] 表示以cur开始的路径中最多有多少个’a’+i。
时间复杂度：每个节点最多处理一次，每次处理，处理它所有的临接表。故时间复杂度：O(E)。E是边数。

代码

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>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		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 CTopSort
{
public:	
	void Init(const vector<vector<int>>& vNeiBo)
	{
		m_c = vNeiBo.size();
		m_vBackNeiBo.resize(m_c);
		vector<int> vOutDeg(m_c);
		for (int cur = 0; cur < m_c; cur++)
		{
			vOutDeg[cur] = vNeiBo[cur].size();	
			for (const auto& next : vNeiBo[cur])
			{
				m_vBackNeiBo[next].emplace_back(cur);
			}
		}
		queue<int> que;
		for (int i = 0; i < m_c; i++)
		{
			if (0 == vOutDeg[i])
			{
				que.emplace(i);
				m_vLeaf.emplace_back(i);
				OnDo(-1, i);
			}
		}

		while (que.size())
		{
			const int cur = que.front();
			que.pop();
			for (const auto& next : m_vBackNeiBo[cur])
			{
				vOutDeg[next]--;
				if (0 == vOutDeg[next])
				{
					que.emplace(next);
					OnDo(cur, next);
				}
			}
		};
	}
	int m_c;
	vector<int> m_vLeaf;
protected:
	virtual void OnDo(int pre, int cur) = 0;
	vector<vector<int>> m_vBackNeiBo;
};

class CMyTopSort : public CTopSort
{
public:
	int Do(string& str, vector<vector<int>>& edges)
	{
		m_str = str;
		m_vLen.assign(str.length(), vector<int>(26));
		m_vNeiBo = CNeiBo::Two(str.length(),edges,true);
		CTopSort::Init(m_vNeiBo);
		if (m_iHasDo < m_c)
		{
			return -1;
		}
		int iMax = 0;
		for (const auto& v : m_vLen)
		{
			iMax = max(iMax, *std::max_element(v.begin(), v.end()));
		}
		return iMax;
	}
	vector<vector<int>> m_vLen;
protected:
	// 通过 CTopSort 继承
	virtual void OnDo(int pre, int cur) override
	{
		m_iHasDo++;
		for (int i = 0; i < 26; i++)
		{
			m_vLen[cur][i] = ('a' + i == m_str[cur]);
			int iMax = 0;
			for (const auto& next : m_vNeiBo[cur])
			{
				iMax = max(iMax, m_vLen[next][i]);
			}
			m_vLen[cur][i] += iMax;
		}
	}
	vector<vector<int>> m_vNeiBo;
	string m_str;	
	int m_iHasDo = 0;
};
class Solution {
public:
	int largestPathValue(string colors, vector<vector<int>>& edges) {
		CMyTopSort top;
		return top.Do(colors, edges);
	}
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	string colors;
	vector<vector<int>> edges;

	{
		Solution sln;
		colors = "abaca", edges = { {0,1},{0,2},{2,3},{3,4} };
		auto res = sln.largestPathValue(colors, edges);
		Assert(3, res);
	}


	{
		Solution sln;
		colors = "a", edges = { {0,0} };
		auto res = sln.largestPathValue(colors, edges);
		Assert(-1, res);
	}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛