• ACM模板二：树、图、并查集、DancingLink

    目录

    〇，全文说明、宏定义代码

    一，二叉树

    1，代码

    2，测试代码

    二，树状数组、线段树

    1，代码

    2，测试代码

    三，多叉树、RMQ、LCA

    1，代码

    2，测试代码

    四，DancingLink、Covering

    1，代码

    2，测试代码

    五，并查集、无向图、最小生成树Kruskal

    1，代码

    2，测试代码

    六，最小生成树Prim

    1，代码

    2，测试代码

    七，有向图、单源最短路径、连通分量、拓扑排序

    1，代码

    2，测试代码

    八，网格图、回路链路、路径重建

    1，代码

    2，测试代码

    〇，全文说明、宏定义代码

    类里面和宏定义处都有接口注释，因为宏不体现具体参数，所以注释以类里面的为准。

    代码工程结构：

    • 每一章的第一节《代码》可以独立编译运行（本地要加LOCAL宏）
    • 每一章的第二节《测试代码》搭配第〇章的代码和本章第一节的代码可以编译运行并测试成功
    • 所有模板文章的第〇章的代码和其他章第一节的《代码》全部汇总起来可以编译运行

    宏定义代码：

    1.  
    2. #define LOCAL //力扣不要本行代码，其他OJ随意
    3.  
    4. ///（1）二叉树///
    5. #define MaxDepth BinaryTree::maxDepth//求二叉树的深度，根节点深度是1
    6. #define MinDepth BinaryTree::minDepth//叶子节点的最小深度
    7. #define PreorderTraversal BinaryTree::preorderTraversal//二叉树的前序遍历
    8. #define PostorderTraversal BinaryTree::postorderTraversal//二叉树的后序遍历
    9. #define InorderTraversal BinaryTree::inorderTraversal//二叉树的中序遍历
    10. #define LevelOrderTraversal BinaryTree::levelOrderTraversal//二叉树的层序遍历
    11. #define BuildTreePre BinaryTree::buildTreePre//根据前序和中序重建二叉树，假设没有重复数字
    12. #define BuildTreePost BinaryTree::buildTreePost//根据中序和后序重建二叉树，假设没有重复数字
    13. #define CountNodes BinaryTree::countNodes//求节点个数
    14. #define CopyTree BinaryTree::copyTree//拷贝二叉树
    15. #define IsSameTree BinaryTree::isSameTree//判断两棵二叉树是否全等
    16. #define InvertTree BinaryTree::invertTree//左右翻转二叉树
    17.  
    18. ///（2）树状数组、线段树///
    19. // TreeArray 树状数组
    20. // TreeArray2D 二维树状数组
    21. // SegmentTree 线段树
    22.  
    23. ///（3）多叉树、RMQ、LCA///
    24. #define EdgesToMultiTree MultiTree::edgesToMultiTree//输入无向图，构造多叉生成树
    25. // TreeWithId 略。//把二叉树或多叉树转成id形式的树，前序遍历，从0开始编号
    26. // RMQ 略。
    27. // LCA 略。
    28.  
    29. ///（4）DancingLink、Covering///
    30. // DancingLink 略。精确覆盖算法
    31. #define GetEdgeCover Covering::getEdgeCover//给定一个2n个点的图，选出n条边，刚好覆盖这2n个点
    32.  
    33. ///（5.1）并查集///
    34. // Union 略。并查集
    35. // UnionDif 略。
    36. // Vunion 略。
    37.  
    38. ///（5.2）无向图///
    39. #define EdgesToBinaryTree UndirectedGraph::edgesToBinaryTree//输入二叉树的边集，生成任意一棵二叉树
    40. #define UndirectedEdgeToFatherList UndirectedGraph::undirectedEdgeToFatherList//无向拓扑排序，输入无向无环图{{1，2}{1，3}{4，3}}的邻接表和指定根1，输出父节点表{4:3, 3:1, 2:1}
    41. #define HasUndirectedCircle UndirectedGraph::hasUndirectedCircle//根据无向图的邻接表判断是否有环
    42. #define IsCompleteGraph UndirectedGraph::isCompleteGraph//判断是不是k-正则图
    43. #define IsTwoDivGraph UndirectedGraph::isTwoDivGraph//判断是不是二分图
    44.  
    45. ///（5.3）最小生成树Kruskal///
    46. #define KruskalMinCostTree Kruskal::kruskalMinCostTree
    47.  
    48. ///（6）最小生成树Prim///
    49. #define PrimminCostTree Prim::minCostConnectPoints
    50.  
    51.  
    52. ///（7.1）有向图///
    53. #define ReverseGraph DirectedGraph::reverseGraph//构建有向图的反向图
    54. #define GetLongestPath DirectedGraph::getLongestPath//求有向无环图中的最长路径长度，出参nextNode是每个点的后继,len是每个点出发的最长路径长度
    55. #define HasDirectedCircle DirectedGraph::hasCircle//根据有向图的邻接表判断是否有环
    56.  
    57. ///（7.2）单源最短路径///
    58. #define DijskraShortestPath Dijskra::shortestPath//求最短路,适用于不存在负权值的边的图
    59. #define BellmanFordShortestPath BellmanFord::shortestPath//求最短路,适用于不存在负权值的环的图
    60. #define SPFAShortestPath SPFA::shortestPath//求最短路,适用于不存在负权值的环的图
    61.  
    62. ///（7.3）不区分有向图和无向图的通用操作///
    63. #define GetSubGraph GraphOpt::getSubGraph//根据点集取子图
    64.  
    65. ///（7.4）连通分量、拓扑排序///
    66. #define SemiConnectComponent SemiConnect::semiConnectComponent//半连通分量分割
    67. #define ConnectComponent KosarajuStrongConnect::connectComponent//Kosaraju算法，强连通分量分割
    68. #define GetPointGraph KosarajuStrongConnect::getPointGraph//强连通分量缩点
    69. // TarjanUndirect 略。Tarjan算法，双连通分量分割
    70. // TarjanStrongConnect 略。Tarjan算法，强连通分量分割
    71. #define TopoSortNoCircle DirectedTopoSort::topoSortNoCircle //有向无环图拓扑排序，输入n=3，g.edges={{0,1}{0,2}{1,2}}, 输出{0,1,2}，有环则输出为空
    72. #define TopoSort DirectedTopoSort::topoSort //有向图拓扑排序
    73.  
    74.  
    75. ///（8.1）网格图///
    76. // GridGraph 略
    77.  
    78. ///（8.2）回路或链路///
    79. // Hierholzer 略。欧拉回路或链路
    80. // Hamilton 略。哈密顿回路或链路
    81.  
    82. ///（8.3）路径重建///
    83. // ReBuild 略。路径重建

    一，二叉树

    1，代码

    1.  
    2. #ifdef LOCAL
    3. #ifndef struct_TreeNode
    4. #define struct_TreeNode
    5. struct TreeNode {
    6. 	int val;
    7. 	TreeNode* left;
    8. 	TreeNode* right;
    9. 	TreeNode() : val(0), left(nullptr), right(nullptr) {}
    10. 	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    11. 	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    12. };
    13. #endif
    14. #endif
    15.  
    16. class BinaryTree
    17. {
    18. public:
    19. 	//求二叉树的深度，根节点深度是1
    20. 	static int maxDepth(TreeNode* root) {
    21. 		if (!root)return 0;
    22. 		return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    23. 	}
    24. 	//叶子节点的最小深度
    25. 	static int minDepth(TreeNode* root) {
    26. 		if (!root)return 0;
    27. 		return min_depth(root);
    28. 	}
    29. 	//二叉树的前序遍历
    30. 	static vector<int> preorderTraversal(TreeNode* root) {
    31. 		vector<int>v1;
    32. 		if (root == NULL)return v1;
    33. 		v1.insert(v1.end(), root->val);
    34. 		vector<int>v2 = preorderTraversal(root->left);
    35. 		v1.insert(v1.end(), v2.begin(), v2.end());
    36. 		v2 = preorderTraversal(root->right);
    37. 		v1.insert(v1.end(), v2.begin(), v2.end());
    38. 		return v1;
    39. 	}
    40. 	//二叉树的后序遍历
    41. 	static vector<int> postorderTraversal(TreeNode* root) {
    42. 		vector<int>v1;
    43. 		if (root == NULL)return v1;
    44. 		vector<int>v2 = postorderTraversal(root->left);
    45. 		v1.insert(v1.end(), v2.begin(), v2.end());
    46. 		v2 = postorderTraversal(root->right);
    47. 		v1.insert(v1.end(), v2.begin(), v2.end());
    48. 		v1.insert(v1.end(), root->val);
    49. 		return v1;
    50. 	}
    51. 	//二叉树的中序遍历
    52. 	static vector<int> inorderTraversal(TreeNode* root) {
    53. 		vector<int>v1;
    54. 		if (root == NULL)return v1;
    55. 		v1 = inorderTraversal(root->left);
    56. 		v1.insert(v1.end(), root->val);
    57. 		vector<int>v2 = inorderTraversal(root->right);
    58. 		v1.insert(v1.end(), v2.begin(), v2.end());
    59. 		return v1;
    60. 	}
    61. 	//二叉树的层序遍历
    62. 	static vectorint>> levelOrderTraversal(TreeNode* root) {
    63. 		vectorint>>ans;
    64. 		if (!root)return ans;
    65. 		vector>v;
    66. 		vectortmp;
    67. 		vector<int>tmpans;
    68. 		tmp.push_back(root);
    69. 		v.push_back(tmp);
    70. 		bfs(v);
    71. 		for (int i = 0; i < v.size(); i++) {
    72. 			tmpans.resize(v[i].size());
    73. 			for (int j = 0; j < v[i].size(); j++)tmpans[j] = v[i][j]->val;
    74. 			ans.push_back(tmpans);
    75. 		}
    76. 		return ans;
    77. 	}
    78. 	//根据前序和中序重建二叉树，假设没有重复数字
    79. 	static TreeNode* buildTreePre(vector<int>& preorder, vector<int>& inorder) {
    80. 		return build_tree(preorder, 0, inorder, 0, inorder.size());
    81. 	}
    82. 	//根据中序和后序重建二叉树，假设没有重复数字
    83. 	static TreeNode* buildTreePost(vector<int>& inorder, vector<int>& postorder) {
    84. 		return build_tree2(postorder, 0, inorder, 0, inorder.size());
    85. 	}
    86. 	//求节点个数
    87. 	static int countNodes(TreeNode* root) {
    88. 		if (!root)return 0;
    89. 		return countNodes(root->left) + countNodes(root->right) + 1;
    90. 	}
    91. 	//拷贝二叉树
    92. 	static TreeNode* copyTree(TreeNode* root)
    93. 	{
    94. 		if (!root)return root;
    95. 		return new TreeNode(root->val, copyTree(root->left), copyTree(root->right));
    96. 	}
    97. 	//判断两棵二叉树是否全等
    98. 	static bool isSameTree(TreeNode* r1, TreeNode* r2)
    99. 	{
    100. 		if (r1 == NULL && r2 == NULL)return true;
    101. 		if (r1 == NULL || r2 == NULL)return false;
    102. 		if (r1->val != r2->val)return false;
    103. 		return isSameTree(r1->left, r2->left) && isSameTree(r1->right, r2->right);
    104. 	}
    105. 	//左右翻转二叉树
    106. 	static TreeNode* invertTree(TreeNode* root) {
    107. 		if (!root)return root;
    108. 		TreeNode* p = root->left, *q = root->right;
    109. 		root->left = q, root->right = p;
    110. 		invertTree(p);
    111. 		invertTree(q);
    112. 		return root;
    113. 	}
    114. private:
    115. 	static int min_depth(TreeNode* root) {
    116. 		if (!root)return 1234567890;
    117. 		if (!root->left && !root->right)return 1;
    118. 		return min(min_depth(root->left), min_depth(root->right)) + 1;
    119. 	}
    120. 	static void bfs(vector>&v) {
    121. 		vectorv1 = *(v.end() - 1);
    122. 		vectorv2;
    123. 		for (int i = 0; i < v1.size(); i++) {
    124. 			if (v1[i]->left)v2.push_back(v1[i]->left);
    125. 			if (v1[i]->right)v2.push_back(v1[i]->right);
    126. 		}
    127. 		if (v2.empty())return;
    128. 		v.push_back(v2);
    129. 		bfs(v);
    130. 	}
    131. 	static TreeNode* build_tree(vector<int>& preorder, int s1, vector<int>& inorder, int s2, int len) {
    132. 		if (len <= 0)return NULL;
    133. 		TreeNode* ans = new TreeNode;
    134. 		ans->val = preorder[s1];
    135. 		auto loc = find(inorder.begin() + s2, inorder.begin() + s2 + len, preorder[s1]);
    136. 		ans->left = build_tree(preorder, s1 + 1, inorder, s2, loc - inorder.begin() - s2);
    137. 		ans->right = build_tree(preorder, loc - inorder.begin() - s2 + s1 + 1, inorder, loc - inorder.begin() + 1, len - (loc - inorder.begin() - s2) - 1);
    138. 		return ans;
    139. 	}
    140. 	static TreeNode* build_tree2(vector<int>& postorder, int s1, vector<int>& inorder, int s2, int len) {
    141. 		if (len <= 0)return NULL;
    142. 		TreeNode* ans = new TreeNode;
    143. 		ans->val = postorder[s1 + len - 1];
    144. 		auto loc = find(inorder.begin() + s2, inorder.begin() + s2 + len, postorder[s1 + len - 1]);
    145. 		ans->left = build_tree2(postorder, s1, inorder, s2, loc - inorder.begin() - s2);
    146. 		ans->right = build_tree2(postorder, loc - inorder.begin() - s2 + s1, inorder, loc - inorder.begin() + 1, len - (loc - inorder.begin() - s2) - 1);
    147. 		return ans;
    148. 	}
    149. };

    2，测试代码

    1. template<typename T>
    2. static bool vecIsSame(const vector& v1, const vector& v2)
    3. {
    4. 	if (v1.size() - v2.size())return false;
    5. 	for (int i = 0; i < v1.size(); i++)if (v1[i] != v2[i])return false;
    6. 	return true;
    7. }
    8. #define EXPECT_VEC_EQ(a,b) if(!vecIsSame((a),(b))){cout<<"ERROR!!!!!!!!!\n";return false;}
    9. #define EXPECT_EQ(a,b) if(a!=b){cout<<"ERROR!!!!!!!!!\n";return false;}
    10.  
    11. bool testBinaryTree()
    12. {
    13. 	TreeNode t1(1), t2(2), t3(3), t4(4);
    14. 	t1.left = &t2, t1.right = &t3, t2.left = &t4;
    15. 	auto p = &t1;
    16. 	EXPECT_EQ(MaxDepth(p), 3);
    17. 	EXPECT_EQ(MinDepth(p), 2);
    18. 	vector<int>pre{ 1, 2, 4, 3 }, post{ 4, 2, 3, 1 }, inorder{ 4, 2, 1, 3 };
    19. 	EXPECT_VEC_EQ(PreorderTraversal(p), pre);
    20. 	EXPECT_VEC_EQ(PostorderTraversal(p), post);
    21. 	EXPECT_VEC_EQ(InorderTraversal(p), inorder);
    22. 	auto p2 = BuildTreePre(pre, inorder);
    23. 	EXPECT_EQ(IsSameTree(p, p2), true);
    24. 	p2 = BuildTreePost(inorder, post);
    25. 	EXPECT_EQ(IsSameTree(p, p2), true);
    26. 	EXPECT_EQ(CountNodes(p), 4);
    27. 	p2 = CopyTree(p);
    28. 	EXPECT_EQ(IsSameTree(p, p2), true);
    29. 	InvertTree(p2);
    30. 	EXPECT_EQ(IsSameTree(p, p2), false);
    31. 	InvertTree(p2);
    32. 	EXPECT_EQ(IsSameTree(p, p2), true);
    33. 	return true;
    34. }
    35.  
    36. int main()
    37. {
    38. 	if (testBinaryTree())cout << "test succ!";
    39. 	return 0;
    40. }

    二，树状数组、线段树

    1，代码

    1.  
    2. template<int maxLen = 100000>
    3. class TreeArray
    4. {
    5. public:
    6. 	TreeArray(int len)//len是元素实际数量,元素id范围是[1,n]
    7. 	{
    8. 		this->n = len;
    9. 		memset(c, 0, sizeof(int)*(len + 1));
    10. 	}
    11. 	void add(int i, int x)
    12. 	{
    13. 		while (i <= n)
    14. 		{
    15. 			c[i] += x;
    16. 			i += (i&(-i));
    17. 		}
    18. 	}
    19. 	int getSum(int i)
    20. 	{
    21. 		int s = 0;
    22. 		while (i)
    23. 		{
    24. 			s += c[i];
    25. 			i -= (i&(-i));
    26. 		}
    27. 		return s;
    28. 	}
    29. private:
    30. 	int n;
    31. 	int c[maxLen+5];
    32. };
    33.  
    34. template<int maxLen = 1000>
    35. class TreeArray2D
    36. {
    37. public:
    38. 	TreeArray2D(int len)//len是元素实际数量,元素id范围是[1,n]*[1,n]
    39. 	{
    40. 		this->n = len;
    41. 		for (int i = 0; i <= n; i++)memset(c[i], 0, sizeof(int)*(n + 1));
    42. 	}
    43. 	void add(int x, int y, int a = 1)
    44. 	{
    45. 		for (int i = x; i <= n; i += (i&(-i)))
    46. 			for (int j = y; j <= n; j += (j&(-j)))c[i][j] += a;
    47. 	}
    48. 	int getSum(int x, int y)
    49. 	{
    50. 		int s = 0;
    51. 		for (int i = x; i > 0; i -= (i&(-i)))
    52. 			for (int j = y; j > 0; j -= (j&(-j)))
    53. 				s += c[i][j];
    54. 		return s;
    55. 	}
    56. private:
    57. 	int n;
    58. 	int c[maxLen +5][maxLen +5];
    59. };
    60.  
    61. //type=0,1,2,3,4分别表示sum型、min型、max型、minId型、maxId型线段树
    62. //maxLen是元素最大数量
    63. template<int type, int maxLen = 100000, typename T = int>
    64. class SegmentTreeBase
    65. {
    66. public:
    67. 	T* getData()//先调getData更新数据再调build
    68. 	{
    69. 		return num;
    70. 	}
    71. 	void build(int len)//len是元素实际数量,元素id范围是[1,n]
    72. 	{
    73. 		this->n = len;
    74. 		build(1, 1, n);
    75. 	}
    76. 	void update(int uplace, T value)//1<=uplace<=n
    77. 	{
    78. 		num[uplace] = value;
    79. 		update(1, 1, n, uplace);
    80. 	}
    81. 	T query(int x, int y)//1<=x<=y<=n
    82. 	{
    83. 		return query(1, 1, n, x, y);
    84. 	}
    85. protected:
    86. 	template<typename T2>
    87. 	inline T2 op(T2 a, T2 b)
    88. 	{
    89. 		if (type == 3)return num[a] < num[b] ? a : b;
    90. 		if (type == 4)return num[a] > num[b] ? a : b;
    91. 		if (type == 0)return a + b;
    92. 		return type == 1 ? min(a, b) : max(a, b);
    93. 	}
    94. 	void build(int key, int low, int high)
    95. 	{
    96. 		if (low == high)
    97. 		{
    98. 			ans[key] = type > 2 ? low : num[low];
    99. 			return;
    100. 		}
    101. 		int mid = (low + high) / 2;
    102. 		build(key * 2, low, mid);
    103. 		build(key * 2 + 1, mid + 1, high);
    104. 		ans[key] = op(ans[key * 2], ans[key * 2 + 1]);
    105. 	}
    106. 	void update(int key, int low, int high, int uplace)
    107. 	{
    108. 		if (low == high)
    109. 		{
    110. 			ans[key] = type > 2 ? low : num[low];
    111. 			return;
    112. 		}
    113. 		int mid = (low + high) / 2;
    114. 		if (uplace <= mid)update(key * 2, low, mid, uplace);
    115. 		else update(key * 2 + 1, mid + 1, high, uplace);
    116. 		ans[key] = op(ans[key * 2], ans[key * 2 + 1]);
    117. 	}
    118. 	T query(int key, int low, int high, int x, int y)
    119. 	{
    120. 		if (low == x && high == y)return ans[key];
    121. 		int mid = (low + high) / 2;
    122. 		if (mid < x)return query(key * 2 + 1, mid + 1, high, x, y);
    123. 		if (mid >= y)return query(key * 2, low, mid, x, y);
    124. 		T a = query(key * 2, low, mid, x, mid);
    125. 		T b = query(key * 2 + 1, mid + 1, high, mid + 1, y);
    126. 		return  op(a, b);
    127. 	}
    128. protected:
    129. 	int n;
    130. 	T num[maxLen + 1];
    131. 	T ans[maxLen * 4 + 10];
    132. };
    133. //sum型线段树拓展，支持查询前缀和
    134. template<int maxLen = 100000, typename T = int>
    135. class SegmentTreeTypeSum :public SegmentTreeBase<0, maxLen, T>
    136. {
    137. 	using BASE = SegmentTreeBase<0, maxLen, T>;
    138. public:
    139. 	int queryPreSum(T x)
    140. 	{
    141. 		return queryPreSum(1, 1, BASE::n, x);
    142. 	}
    143. private:
    144. 	int queryPreSum(int key, int low, int high, T x)
    145. 	{
    146. 		if (low == high)return low;
    147. 		int mid = (low + high) / 2;
    148. 		if (x <= BASE::ans[key * 2])return queryPreSum(key * 2, low, mid, x);
    149. 		return queryPreSum(key * 2 + 1, mid + 1, high, x - BASE::ans[key * 2]);
    150. 	}
    151. };
    152. //5种线段树拓展，支持区间更新，区间查询
    153. template<int type, int maxLen = 100000, typename T = int, T invalid = -1>
    154. class SegmentTree :public SegmentTreeBase
    155. {
    156. 	using BASE = SegmentTreeBase;
    157. public:
    158. 	void build(int len)//len是元素实际数量,元素id范围是[1,n]
    159. 	{
    160. 		BASE::n = len;
    161. 		build(1, 1, BASE::n);
    162. 	}
    163. 	void update(int uplace, T value)//1<=uplace<=n，覆盖父类函数
    164. 	{
    165. 		update(uplace, uplace, value);
    166. 	}
    167. 	void update(int x, int y, T value)//1<=x<=y<=n
    168. 	{
    169. 		update(1, 1, BASE::n, x, y, value);
    170. 	}
    171. 	T query(int x, int y)//1<=x<=y<=n
    172. 	{
    173. 		return query(1, 1, BASE::n, x, y);
    174. 	}
    175. private:
    176. 	static inline T opMulti(T a, int num)
    177. 	{
    178. 		if (!type)return a * num;
    179. 		return a;
    180. 	}
    181. 	void build(int key, int low, int high)
    182. 	{
    183. 		if (low == high)
    184. 		{
    185. 			BASE::ans[key] = type > 2 ? low : BASE::num[low];
    186. 			lazy[key] = invalid;
    187. 			return;
    188. 		}
    189. 		int mid = (low + high) / 2;
    190. 		build(key * 2, low, mid);
    191. 		build(key * 2 + 1, mid + 1, high);
    192. 		BASE::ans[key] = BASE::op(BASE::ans[key * 2], BASE::ans[key * 2 + 1]);
    193. 		lazy[key] = invalid;
    194. 	}
    195. 	void update(int key, int low, int high, int x, int y, T value)
    196. 	{
    197. 		if (low == x && high == y)
    198. 		{
    199. 			BASE::ans[key] = type > 2 ? x : opMulti(value, high - low + 1);
    200. 			lazy[key] = value;
    201. 			if (x == y)BASE::num[x] = value;
    202. 			return;
    203. 		}
    204. 		if (lazy[key] != invalid)down(key, low, high);
    205. 		int mid = (low + high) / 2;
    206. 		if (mid < x)update(key * 2 + 1, mid + 1, high, x, y, value);
    207. 		else if (mid >= y)update(key * 2, low, mid, x, y, value);
    208. 		else
    209. 		{
    210. 			update(key * 2, low, mid, x, mid, value);
    211. 			update(key * 2 + 1, mid + 1, high, mid + 1, y, value);
    212. 		}
    213. 		BASE::ans[key] = BASE::op(BASE::ans[key * 2], BASE::ans[key * 2 + 1]);
    214. 	}
    215. 	void down(int key, int low, int high)
    216. 	{
    217. 		int mid = (low + high) / 2;
    218. 		BASE::ans[key * 2] = type > 2 ? low : opMulti(lazy[key], mid - low + 1);
    219. 		BASE::ans[key * 2 + 1] = type > 2 ? high : opMulti(lazy[key], high - mid);
    220. 		lazy[key * 2] = lazy[key];
    221. 		lazy[key * 2 + 1] = lazy[key];
    222. 		lazy[key] = invalid;
    223. 	}
    224. 	T query(int key, int low, int high, int x, int y)
    225. 	{
    226. 		if (low == x && high == y)return BASE::ans[key];
    227. 		if (lazy[key] != invalid) {
    228. 			return type > 2 ? x : opMulti(lazy[key], y - x + 1);
    229. 		}
    230. 		int mid = (low + high) / 2;
    231. 		if (mid < x)return query(key * 2 + 1, mid + 1, high, x, y);
    232. 		if (mid >= y)return query(key * 2, low, mid, x, y);
    233. 		T a = query(key * 2, low, mid, x, mid);
    234. 		T b = query(key * 2 + 1, mid + 1, high, mid + 1, y);
    235. 		return BASE::op(a, b);
    236. 	}
    237. private:
    238. 	T lazy[maxLen * 4 + 10];
    239. };

    2，测试代码

    1.  
    2. #define EXPECT_EQ(a,b) if(a!=b){cout<<"ERROR!!!!!!!!!\n";return false;}
    3.  
    4. bool testTreeArray()
    5. {
    6. 	TreeArray<> t(100);
    7. 	t.add(1, 5);
    8. 	t.add(3, 10);
    9. 	EXPECT_EQ(t.getSum(1), 5);
    10. 	EXPECT_EQ(t.getSum(100), 15);
    11. 	return true;
    12. }
    13. bool testSegmentTree()
    14. {
    15. 	SegmentTreeTypeSum<10000> st;
    16. 	int* num = st.getData();
    17. 	num[1] = 3, num[2] = 4, num[3] = 2, num[4] = 6;
    18. 	st.build(4);
    19. 	st.update(1, 5); //5 4 2 6
    20. 	EXPECT_EQ(st.query(1, 3), 11);
    21. 	EXPECT_EQ(st.queryPreSum(5), 1);
    22. 	EXPECT_EQ(st.queryPreSum(9), 2);
    23. 	EXPECT_EQ(st.queryPreSum(11), 3);
    24. 	SegmentTree<1, 10000> stMin;
    25. 	num = stMin.getData();
    26. 	num[1] = 3, num[2] = 4, num[3] = 2, num[4] = 6;
    27. 	stMin.build(4);
    28. 	stMin.update(2, 3, 5);//3 5 5 6
    29. 	EXPECT_EQ(stMin.query(1, 4), 3);
    30. 	EXPECT_EQ(stMin.query(3, 4), 5);
    31. 	return true;
    32. }
    33. bool test2()
    34. {
    35. 	return testTreeArray() && testSegmentTree();
    36. }
    37.  
    38. int main()
    39. {
    40. 	if (test2())cout << "test succ!";
    41. 	return 0;
    42. }

    三，多叉树、RMQ、LCA

    1，代码

    1.  
    2. #ifdef LOCAL
    3. #ifndef struct_TreeNode
    4. #define struct_TreeNode
    5. struct TreeNode {
    6. 	int val;
    7. 	TreeNode* left;
    8. 	TreeNode* right;
    9. 	TreeNode() : val(0), left(nullptr), right(nullptr) {}
    10. 	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    11. 	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    12. };
    13. #endif
    14. #endif
    15.  
    16. struct MultiTreeNode {
    17. 	int val = 0;
    18. 	vectorson{}; //son只存实际有的孩子，son可能为空
    19. 	MultiTreeNode() {}
    20. 	MultiTreeNode(int x) : val(x) {}
    21. };
    22.  
    23. class MultiTree {
    24. public:
    25. 	//输入连通的无向图的邻接表，构造一棵多叉生成树，val存放原id
    26. 	static MultiTreeNode* edgesToMultiTree(map<int, vector<int>>&m)
    27. 	{
    28. 		map<int, int>visit;
    29. 		map<int, MultiTreeNode*>mt;
    30. 		int x = m.begin()->first;
    31. 		queue<int>q;
    32. 		q.push(x);
    33. 		visit[x] = 1;
    34. 		mt[x] = new MultiTreeNode(x);
    35. 		while (!q.empty()) {
    36. 			int id = q.front();
    37. 			q.pop();
    38. 			for (auto x : m[id]) {
    39. 				if (visit[x])continue;
    40. 				q.push(x);
    41. 				visit[x] = 1;
    42. 				mt[id]->son.push_back(mt[x] = new MultiTreeNode(x));
    43. 			}
    44. 		}
    45. 		return mt[x];
    46. 	}
    47. };
    48.  
    49. //把二叉树或多叉树转成id形式的树，前序遍历，从0开始编号
    50. class TreeWithId
    51. {
    52. public:
    53. 	unordered_map<int, vector<int>>sons;//所有子节点的编号，其中根节点编号=0
    54. 	unordered_map<int, int>vals;//节点权值
    55. 	TreeWithId(TreeNode* root) {
    56. 		if (root)dfs(root);
    57. 	}
    58. 	TreeWithId(MultiTreeNode* root) {
    59. 		if (root)dfs(root);
    60. 	}
    61. 	unordered_mapint>m;//原指针对应在新树中的编号
    62. 	unordered_mapint>m2;
    63. private:	
    64. 	inline void dfs(TreeNode* root) {
    65. 		if (m.find(root) == m.end())m[root] = m.size();
    66. 		vals[m[root]] = root->val;
    67. 		if (root->left)dfs(root->left), sons[m[root]].push_back(m[root->left]);
    68. 		if (root->right)dfs(root->right), sons[m[root]].push_back(m[root->right]);
    69. 	}	
    70. 	inline void dfs(MultiTreeNode* root) {
    71. 		if (m2.find(root) == m2.end())m2[root] = m2.size();
    72. 		vals[m2[root]] = root->val;
    73. 		for (auto p : root->son)dfs(p), sons[m2[root]].push_back(m2[p]);
    74. 	}
    75. };
    76.  
    77.  
    78. //type=1是求最小值，=2是求最大值, =3是minId，=4是maxId
    79. template<int type, typename T = int>
    80. class RMQ
    81. {
    82. public:
    83. 	RMQ() {}
    84. 	RMQ(const vector& data) {
    85. 		this->data = data;
    86. 		len = data.size();
    87. 		logLen = getLength(len + 5);
    88. 		init(data);
    89. 	}
    90. 	inline T getMinMax(int low, int high) { //求[low,high]内的最值，0<=low<=high
    91. 		if (low == high)return v[low][0];
    92. 		int j = getLength(high - low) - 1;
    93. 		return opt(v[high + 1 - (1 << j)][j], v[low][j]);
    94. 	}
    95. 	inline int getMinMaxId(int low, int high) { //求[low,high]内的最值的id，0<=low<=high
    96. 		if (low == high)return v[low][0];
    97. 		int j = getLength(high - low) - 1;
    98. 		return optId(v[high + 1 - (1 << j)][j], v[low][j]);
    99. 	}
    100. private:
    101. 	void init(const vector& data) {
    102. 		v.resize(len);
    103. 		for (int i = 0; i < v.size(); i++) {
    104. 			v[i].resize(logLen);
    105. 			if (type <= 2)v[i][0] = data[i];
    106. 			else v[i][0] = i;
    107. 		}
    108. 		for (int j = 1; j < logLen; j++)
    109. 		{
    110. 			for (int i = 0; i < len; i++)
    111. 			{
    112. 				v[i][j] = v[i][j - 1];
    113. 				int k = i + (1 << (j - 1));
    114. 				if (k >= len)continue;
    115. 				if (type <= 2) v[i][j] = opt(v[i][j], v[k][j - 1]);
    116. 				else v[i][j] = optId(v[i][j], v[k][j - 1]);
    117. 			}
    118. 		}
    119. 	}
    120. 	static inline T opt(T x, T y) {
    121. 		return type == 1 ? min(x, y) : max(x, y);
    122. 	}
    123. 	inline T optId(int x, int y) {
    124. 		if (type == 3) {
    125. 			return data[x] < data[y] ? x : y;
    126. 		}
    127. 		return data[x] < data[y] ? y : x;
    128. 	}
    129. 	//二进制总位数
    130. 	static inline int getLength(int n) {
    131. 		int ans = 0;
    132. 		while (n)
    133. 		{
    134. 			n >>= 1;
    135. 			ans++;
    136. 		}
    137. 		return ans;
    138. 	}
    139. private:
    140. 	vectordata;
    141. 	vector>v;
    142. 	int len, logLen;
    143. };
    144. class LCA {
    145. public:
    146. 	LCA(TreeWithId tree) {
    147. 		int n = tree.vals.size();
    148. 		visitn.resize(n);
    149. 		visitDeep.resize(n * 2 - 1);
    150. 		ids.resize(n * 2 - 1);
    151. 		dfs(tree, 0, 1);
    152. 		opt = RMQ<3>(visitDeep);
    153. 	}
    154. 	//输入2个节点的id，输出最近公共祖先的id
    155. 	int getLca(int x, int y)
    156. 	{
    157. 		x = visitn[x], y = visitn[y];
    158. 		if (x > y)x ^= y ^= x ^= y;
    159. 		int minId = opt.getMinMaxId(x, y); //求最小深度对应的遍历数
    160. 		return ids[minId];
    161. 	}
    162. private:
    163. 	void dfs(TreeWithId& tree, int k, int d)
    164. 	{
    165. 		for (auto p : tree.sons[k])
    166. 		{
    167. 			visitDeep[vnum] = d;
    168. 			ids[vnum++] = k;
    169. 			dfs(tree, p, d + 1);
    170. 		}
    171. 		visitn[k] = vnum; //存入每个点的任意一个遍历数
    172. 		visitDeep[vnum] = d; //存入遍历数对应的深度
    173. 		ids[vnum++] = k; //存入遍历数对应的节点id
    174. 	}
    175. 	vector<int> visitDeep;
    176. 	vector<int> visitn;
    177. 	vector<int> ids;
    178. 	int vnum = 0;
    179. 	RMQ<3>opt;
    180. };

    2，测试代码

    1. bool test3() //待完善
    2. {
    3. 	TreeNode* root = new TreeNode(0);
    4. 	TreeWithId tree{ root };
    5. 	RMQ<1>{};
    6. 	LCA lca(tree);
    7. 	return true;
    8. }
    9.  
    10. int main()
    11. {
    12. 	if (test3())cout << "test succ!";
    13. 	return 0;
    14. }

    四，DancingLink、Covering

    1，代码

    1. class DancingLink // 精确覆盖算法
    2. {
    3. public:
    4. 	DancingLink(int m, int n, int maxNum) //01矩阵的行、列、1的最大数量
    5. 	{
    6. 		this->m = m, this->n = n, maxNum += n + 1;
    7. 		rhead.resize(m + 1), nums.resize(n + 1);
    8. 		row.resize(maxNum), col.resize(maxNum);
    9. 		up.resize(maxNum), down.resize(maxNum), lef.resize(maxNum), rig.resize(maxNum);
    10. 		sc.resize(m), rows.resize(m);
    11. 		for (int i = 0; i <= n; i++)
    12. 		{
    13. 			up[i] = i, down[i] = i;
    14. 			lef[i] = i - 1, rig[i] = i + 1;
    15. 			row[i] = 0, col[i] = i, nums[i] = 0;
    16. 		}
    17. 		lef[0] = n, rig[n] = 0, nums[0] = INT_MAX;
    18. 		key = n;
    19. 		for (int i = 0; i <= m; i++)rhead[i] = 0;
    20. 	}
    21. 	void push(int r, int c)//新增坐标在(r,c)的一个节点
    22. 	{
    23. 		row[++key] = r, col[key] = c;
    24. 		up[key] = c, down[key] = down[c];
    25. 		up[down[c]] = key, down[c] = key;
    26. 		if (rhead[r] == 0)rhead[r] = lef[key] = rig[key] = key;
    27. 		else
    28. 		{
    29. 			lef[key] = rhead[r], rig[key] = rig[rhead[r]];
    30. 			lef[rig[rhead[r]]] = key, rig[rhead[r]] = key;
    31. 		}
    32. 		nums[c]++;
    33. 	}
    34. 	vectorint>> getAllAns()
    35. 	{
    36. 		return dfs(false);
    37. 	}
    38. 	vector<int> getAnyAns()
    39. 	{
    40. 		auto v = dfs(true);
    41. 		if (v.size())return v[0];
    42. 		return vector<int>{};
    43. 	}
    44. private:
    45. 	vectorint>> dfs(bool onlyOne)
    46. 	{
    47. 		vectorint>>ans;
    48. 		while (true) {
    49. 			if (rig[0] == 0) {
    50. 				rows.resize(rowsid);
    51. 				ans.push_back(rows);
    52. 				rows.resize(m);
    53. 				if (onlyOne)return ans;
    54. 			}
    55. 			int c = min_element(nums.begin() + 1, nums.end()) - nums.begin();
    56. 			if (rig[0] == 0)c = 0;
    57. 			del(c);
    58. 			while (true) {
    59. 				c = down[c];
    60. 				if (c > n)break;
    61. 				reback(col[c]);
    62. 				if (scid == 0)return ans;
    63. 				c = sc[--scid];
    64. 				rowsid--;
    65. 				for (int j = rig[c]; j != c; j = rig[j])reback(col[j]);
    66. 			}
    67. 			sc[scid++] = c;//记录选中id
    68. 			rows[rowsid++] = row[c];
    69. 			for (int j = rig[c]; j != c; j = rig[j])del(col[j]);
    70. 		}
    71. 		return ans;
    72. 	}
    73. 	inline void del(int c)//删除第c列的所有元素和他们所在行的所有元素
    74. 	{
    75. 		lef[rig[c]] = lef[c], rig[lef[c]] = rig[c];
    76. 		for (int i = down[c]; i != c; i = down[i])
    77. 			for (int j = rig[i]; j != i; j = rig[j])
    78. 				down[up[j]] = down[j], up[down[j]] = up[j], nums[col[j]]--;
    79. 		nums[c] = INT_MAX;
    80. 	}
    81. 	inline void reback(int c)//完全回退del操作
    82. 	{
    83. 		lef[rig[c]] = rig[lef[c]] = c, nums[c] = 0;
    84. 		for (int i = down[c]; i != c; i = down[i]) {
    85. 			for (int j = rig[i]; j != i; j = rig[j])
    86. 				down[up[j]] = up[down[j]] = j, nums[col[j]]++;
    87. 			nums[c]++;
    88. 		}
    89. 	}
    90. private:
    91. 	int m, n, key;
    92. 	vector<int>row, col;//每个节点的行，列
    93. 	vector<int>rhead;//每行第一个节点的id
    94. 	vector<int>up, down, lef, rig;//每个节点上下左右的节点id
    95. 	vector<int>nums;//每一列的元素个数
    96. 	vector<int>sc;
    97. 	int scid = 0, rowsid = 0;
    98. 	vector<int>rows;//覆盖选中的行，值的范围是从1到m
    99. };
    100. #ifndef struct_UndirectedEdge
    101. #define struct_UndirectedEdge
    102. template<typename T = int>
    103. struct UndirectedEdge
    104. {
    105. 	UndirectedEdge() {
    106. 		a = b = dist = 0;
    107. 	};
    108. 	UndirectedEdge(const vector<int>&v) {
    109. 		a = v[0], b = v[1], dist = 0;
    110. 		if (v.size() > 2)dist = v[2];
    111. 	}
    112. 	int a;//端点a的id
    113. 	int b;//端点b的id
    114. 	T dist;//ab之间的距离
    115. };
    116. #endif
    117. class Covering {
    118. public:
    119. 	//给定一个2n个点的图，选出n条边，刚好覆盖这2n个点，返回所有的解
    120. 	static vectorint>>> getEdgeCover(int n, vectorint>> &v)
    121. 	{
    122. 		DancingLink d(v.size(), n * 2, v.size() * 2);
    123. 		for (int i = 0; i < v.size(); i++) {
    124. 			d.push(i, v[i].a + 1);
    125. 			d.push(i, v[i].b + 1);
    126. 		}
    127. 		vectorint>>>ans;
    128. 		vectorint>> vrow = d.getAllAns();
    129. 		for (auto vi : vrow) {
    130. 			vectorint>>vans; //getNumFromId(v, vi)
    131. 			transform(vi.begin(), vi.end(), std::back_inserter(vans), [&](int id) {return v[id]; });
    132. 			ans.push_back(vans);
    133. 		}
    134. 		return ans;
    135. 	}
    136. };

    2，测试代码

    1.  
    2. bool testDancingLink()//待完善
    3. {
    4. 	return true;
    5. }
    6. bool testCovering()//待完善
    7. {
    8. 	return true;
    9. }
    10. int main()
    11. {
    12. 	if (testDancingLink() && testCovering())cout << "test succ!";
    13. 	return 0;
    14. }

    五，并查集、无向图、最小生成树Kruskal

    1，代码

    1. class Union //并查集
    2. {
    3. public:
    4. 	Union(int num, bool canZip = true, int startId = 0) //startId一般是0或1,可以大于1,不能太大
    5. 	{
    6. 		fa.resize(num + startId);
    7. 		for (int i = startId; i < fa.size(); i++)fa[i] = i;
    8. 		this->canZip = canZip;
    9. 		this->startId = startId;
    10. 	}
    11. 	virtual int find(int x)	//找祖先,canZip控制能否做路径压缩加速
    12. 	{
    13. 		if (canZip) {
    14. 			if (fa[x] == x)return x;
    15. 			return fa[x] = find(fa[x]);
    16. 		}
    17. 		int r = x;
    18. 		while (fa[r] != r)r = fa[r];
    19. 		return r;
    20. 	}
    21. 	bool inSame(int x, int y)//是否位于同一个集合
    22. 	{
    23. 		return find(x) == find(y);
    24. 	}
    25. 	void merge(int x, int y)//合并2个集合，如果是同一个集合则不做操作
    26. 	{
    27. 		if (!inSame(x, y))fa[find(x)] = y;
    28. 	}
    29. 	vector<int> getRoots()//获取所有根节点
    30. 	{
    31. 		vector<int>ans;
    32. 		ans.reserve(fa.size());
    33. 		for (int i = startId; i < fa.size(); i++)if (fa[i] == i)ans.push_back(i);
    34. 		return ans;
    35. 	}
    36. 	int getRootNums()//统计根节点数目
    37. 	{
    38. 		return getRoots().size();
    39. 	}
    40. 	vectorint>> getGroups()
    41. 	{
    42. 		vector<int> roots = getRoots();
    43. 		map<int, int>m = reflect(roots);
    44. 		vectorint>>ans(m.size());
    45. 		for (int i = startId; i < fa.size(); i++)ans[m[find(i)]].push_back(i);
    46. 		return ans;
    47. 	}
    48. protected:
    49. 	template<typename T>
    50. 	mapint> reflect(const vector& v)
    51. 	{
    52. 		mapint>m;
    53. 		for (int i = 0; i < v.size(); i++)m[v[i]] = i;
    54. 		return m;
    55. 	}
    56. protected:
    57. 	vector<int>fa;
    58. 	bool canZip;
    59. 	int startId;
    60. };
    61. class UnionDif :public Union //差分版并查集，依赖路径压缩
    62. {
    63. public:
    64. 	UnionDif(int num, int startId = 0) :Union{ num,true,startId } {}
    65. 	int find(int x)	//找祖先
    66. 	{
    67. 		if (fa[x] == x)return x;
    68. 		find(fa[x]);
    69. 		dif[x] += dif[fa[x]];
    70. 		fa[x] = fa[fa[x]];
    71. 		return fa[x];
    72. 	}
    73. 	void merge(int x, int y, double xSubY = 0)//合并2个集合，如果是同一个集合则不做操作
    74. 	{
    75. 		if (inSame(x, y))return;
    76. 		find(x);
    77. 		dif[fa[x]] = xSubY - dif[x];
    78. 		fa[fa[x]] = y;
    79. 		return;
    80. 	}
    81. 	double getDif(int x)
    82. 	{
    83. 		return dif[x];
    84. 	}
    85. private:
    86. 	map<int, double>dif;//每个节点和fa的差分
    87. };
    88. template<typename T>
    89. class Vunion:public Union //集合并查集
    90. {
    91. public:
    92. 	Vunion(int num) :Union{ num } {};
    93. 	void push(vector>&v) {
    94. 		mapint>>m;
    95. 		for (int i = 0; i < v.size(); i++)for (auto x : v[i])m[x].push_back(i);
    96. 		for (auto &p : m) {
    97. 			for (auto x : p.second)merge(x, p.second[0]);
    98. 		}
    99. 	}
    100. };
    101.  
    102.  
    103. #ifdef LOCAL
    104. #ifndef struct_TreeNode
    105. #define struct_TreeNode
    106. struct TreeNode {
    107. 	int val;
    108. 	TreeNode* left;
    109. 	TreeNode* right;
    110. 	TreeNode() : val(0), left(nullptr), right(nullptr) {}
    111. 	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    112. 	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    113. };
    114. #endif
    115. #endif
    116.  
    117. #ifndef struct_UndirectedEdge
    118. #define struct_UndirectedEdge
    119. template<typename T = int>
    120. struct UndirectedEdge
    121. {
    122. 	UndirectedEdge() {
    123. 		a = b = dist = 0;
    124. 	};
    125. 	UndirectedEdge(const vector<int>&v) {
    126. 		a = v[0], b = v[1], dist = 0;
    127. 		if (v.size() > 2)dist = v[2];
    128. 	}
    129. 	int a;//端点a的id
    130. 	int b;//端点b的id
    131. 	T dist;//ab之间的距离
    132. };
    133. #endif
    134. template<typename T = int>
    135. struct UndirectedGraphData
    136. {
    137. public:
    138. 	vector>edges; //边集，无法表示孤立点，一条边只出现一次
    139. 	mapint, int>, T>edgeMap; //边集，无法表示孤立点，一条边出现两次
    140. 	map<int, vector<int>>adjaList;//邻接表，孤立点是否出现取决于allPointFlag，一条边两个点都出现在对方的邻接表中
    141. 	bool allPointFlag = false;//默认邻接表中不含孤立点
    142. 	int startId = 0;
    143. public:
    144. 	UndirectedGraphData() {
    145. 	}
    146. 	UndirectedGraphData(const vector>&edges) {
    147. 		this->edges = edges;
    148. 		adjaList = undirectedEdgeToAdjaList(edges);
    149. 		edgeMap = undirectedEdgeToValueMap(edges);
    150. 	}
    151. 	UndirectedGraphData( vectorint>>& edges) { //仅限没有权值或者权值为整数的图
    152. 		transform(edges.begin(), edges.end(), std::back_inserter(this->edges), [](const vector<int>& v) {return UndirectedEdge<int>{v}; });
    153. 		adjaList = undirectedEdgeToAdjaList(this->edges);
    154. 		edgeMap = undirectedEdgeToValueMap(this->edges);
    155. 	}
    156. 	UndirectedGraphData(const map<int, vector<int>>& adjaList) { //仅限没有权值的图
    157. 		this->adjaList = adjaList;
    158. 		for (auto& v : this->adjaList) {
    159. 			for (auto vi : v.second)if (v.first < vi)edges.push_back(UndirectedEdge(vector<int>{v.first, vi, 0}));
    160. 		}
    161. 		edgeMap = undirectedEdgeToValueMap(edges);
    162. 	}
    163. 	void setNumV(int n, int startId = 0) { //startId一般是0或1,可以大于1
    164. 		allPointFlag = true;
    165. 		for (int i = startId; i < startId + n; i++)adjaList[i];
    166. 		this->startId = startId;
    167. 	}
    168. 	int getNumV() const {
    169. 		return adjaList.size();
    170. 	}
    171. 	int getNumE() const {
    172. 		return edges.size();
    173. 	}
    174. private:
    175. 	//输入无向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{1,3},3:{1,2}}
    176. 	static map<int, vector<int>> undirectedEdgeToAdjaList(const vector>& v)
    177. 	{
    178. 		map<int, vector<int>> ans;
    179. 		for (auto& vi : v) {
    180. 			ans[vi.a].push_back(vi.b);
    181. 			ans[vi.b].push_back(vi.a);
    182. 		}
    183. 		return ans;
    184. 	}
    185. 	//输入无向带权边集，输出边和权的映射
    186. 	static mapint, int>, T> undirectedEdgeToValueMap(const vector>& v)
    187. 	{
    188. 		mapint, int>, T>m;
    189. 		for (auto& vi : v) {
    190. 			m[{vi.a, vi.b}] = vi.dist;
    191. 			m[{vi.b, vi.a}] = vi.dist;
    192. 		}
    193. 		return m;
    194. 	}
    195. };
    196. class UndirectedGraph
    197. {
    198. public:
    199. 	//输入二叉树的边集，生成任意一棵二叉树，val存放原id
    200. 	static TreeNode* edgesToBinaryTree(vectorint>>& edges)
    201. 	{
    202. 		map<int, int>ids;
    203. 		for (auto &e : edges) {
    204. 			for (int i = 0; i <= 1; i++) {
    205. 				if (ids.find(e[i]) == ids.end())ids[e[i]] = ids.size();
    206. 			}
    207. 		}
    208. 		map<int, vector<int>>m;
    209. 		Union un(ids.size());
    210. 		for (auto &e : edges) {
    211. 			int id0 = ids[e[0]], id1 = ids[e[1]];
    212. 			if (!un.inSame(id0, id1)) {
    213. 				un.merge(id0, id1);
    214. 				m[e[0]].push_back(e[1]);
    215. 				m[e[1]].push_back(e[0]);
    216. 			}
    217. 		}
    218. 		int id = -12345;
    219. 		for (auto &mi : m)if (mi.second.size() < 3) {
    220. 			id = mi.first;
    221. 			break;
    222. 		}
    223. 		if (id == -12345)return nullptr;
    224. 		map<int, int>visit;
    225. 		TreeNode* ans = new TreeNode(id);
    226. 		queueq;
    227. 		q.push(ans);
    228. 		while (!q.empty()) {
    229. 			TreeNode* p = q.front();
    230. 			q.pop();
    231. 			visit[p->val] = 1;
    232. 			for (auto x : m[p->val])if (visit[x] == 0) {
    233. 				TreeNode* p2 = new TreeNode(x);
    234. 				q.push(p2);
    235. 				if (!p->left)p->left = p2;
    236. 				else p->right = p2;
    237. 			}
    238. 		}
    239. 		return ans;
    240. 	}
    241. 	//无向拓扑排序，输入无向无环图{{1，2}{1，3}{4，3}}的邻接表和指定根1，输出父节点表{4:3, 3:1, 2:1}
    242. 	static map<int, int> undirectedEdgeToFatherList(UndirectedGraphData<int> &g, int root)
    243. 	{
    244. 		auto& m = g.adjaList;
    245. 		map<int, int>visit;
    246. 		map<int, int>fa;
    247. 		queue<int>q;
    248. 		q.push(root);
    249. 		visit[root] = 1;
    250. 		while (!q.empty()) {
    251. 			int id = q.front();
    252. 			q.pop();
    253. 			for (auto c : m[id]) {
    254. 				if (visit[c] == 0)q.push(c), fa[c] = id;
    255. 				visit[c] = 1;
    256. 			}
    257. 		}
    258. 		return fa;
    259. 	}
    260. 	//根据无向图的邻接表判断是否有环
    261. 	static bool hasUndirectedCircle(const UndirectedGraphData<int>& g)
    262. 	{
    263. 		auto& m = g.adjaList;
    264. 		vector<int>keys; //auto keys = getFirst(m);
    265. 		transform(m.begin(), m.end(), std::back_inserter(keys), [](const pair<int, vector<int>>& p) {return p.first; });
    266. 		int minkey = *min_element(keys.begin(), keys.end());
    267. 		int maxKey = *max_element(keys.begin(), keys.end());
    268. 		Union unions(maxKey - minkey + 1);
    269. 		mapint, int>, int>mp;
    270. 		for (auto& mi : m) {
    271. 			for (auto k : mi.second) {
    272. 				if (mp[make_pair(k, mi.first)])continue;
    273. 				if (unions.inSame(k - minkey, mi.first - minkey))return true;
    274. 				unions.merge(k - minkey, mi.first - minkey);
    275. 				mp[make_pair(mi.first, k)] = 1;
    276. 			}
    277. 		}
    278. 		return false;
    279. 	}
    280. 	//判断是不是k-正则图
    281. 	static bool isCompleteGraph(int k, UndirectedGraphData<int> &g)
    282. 	{
    283. 		for (auto &mi : g.adjaList) {
    284. 			if (mi.second.size() != k)return false;
    285. 		}
    286. 		return true;
    287. 	}
    288. 	//判断是不是二分图, 节点编号是0到n-1
    289. 	static bool isTwoDivGraph(int n, UndirectedGraphData<int> &g) {
    290. 		UnionDif unions(n);
    291. 		for (auto e : g.edges) {
    292. 			unions.find(e.a);
    293. 			unions.find(e.b);
    294. 			if (unions.inSame(e.a, e.b)) {
    295. 				if (int(unions.getDif(e.a) + unions.getDif(e.b)) % 2)return false;
    296. 			}
    297. 			else {
    298. 				unions.merge(e.a, e.b, 1);
    299. 			}
    300. 		}
    301. 		return true;
    302. 	}
    303. };
    304.  
    305. class Kruskal
    306. {
    307. public:
    308. 	//计算最小生成树，结果按照边从小到大排序,出参treeNum是森林中树的数量
    309. 	static vectorint>> kruskalMinCostTree(int n, vectorint>>& v, int& treeNum)
    310. 	{
    311. 		sort(v.begin(), v.end(), cmp);
    312. 		Union unions(n);
    313. 		vectorint>>ans;
    314. 		for (int i = 0, j = 0; j < n - 1 && i < v.size(); i++)
    315. 		{
    316. 			if (unions.inSame(v[i].a, v[i].b))continue;
    317. 			unions.merge(v[i].a, v[i].b);
    318. 			ans.push_back(v[i]);
    319. 			j++;
    320. 		}
    321. 		treeNum = unions.getRootNums();
    322. 		return ans;
    323. 	}
    324. private:
    325. 	static bool cmp(UndirectedEdge<int>& a, UndirectedEdge<int>& b)
    326. 	{
    327. 		return a.dist < b.dist;
    328. 	}
    329. };

    2，测试代码

    1. template<typename T>
    2. static bool vecIsSame(const vector& v1, const vector& v2)
    3. {
    4. 	if (v1.size() - v2.size())return false;
    5. 	for (int i = 0; i < v1.size(); i++)if (v1[i] != v2[i])return false;
    6. 	return true;
    7. }
    8. #define EXPECT_VEC_EQ(a,b) if(!vecIsSame((a),(b))){cout<<"ERROR!!!!!!!!!\n";return false;}
    9.  
    10. bool testUnion()
    11. {
    12. 	Union u(5);
    13. 	EXPECT_VEC_EQ(u.getRoots(), (vector<int>{0, 1, 2, 3, 4}));
    14. 	u.merge(1, 2);
    15. 	u.merge(1, 1);
    16. 	u.merge(3, 3);
    17. 	EXPECT_VEC_EQ(u.getRoots(), (vector<int>{0, 2, 3, 4}));
    18. 	u.merge(4, 3);
    19. 	auto v = u.getRoots();
    20. 	EXPECT_VEC_EQ(u.getRoots(), (vector<int>{0, 2, 3}));
    21. 	return true;
    22. }
    23. bool testUndirectedGraph()//待完善
    24. {
    25. 	return true;
    26. }
    27. bool testKruskal()//待完善
    28. {
    29. 	Kruskal{};
    30. 	return true;
    31. }
    32. bool test4()
    33. {
    34. 	return testUnion() && testUndirectedGraph() && testKruskal();
    35. }
    36.  
    37. int main()
    38. {
    39. 	if (test4())cout << "test succ!";
    40. 	return 0;
    41. }

    六，最小生成树Prim

    1，代码

    1.  
    2. class Prim
    3. {
    4. public:
    5. 	//计算最小生成树，结果按照边从小到大排序
    6. 	static vectorint, int>> minCostConnectPoints(int n, mapint, int>, int>& value)
    7. 	{
    8. 		vector<bool>visit_(n);
    9. 		vector<int>minLen(n);
    10. 		for (int i = 0; i < n; i++) {
    11. 			minLen[i] = INT_MAX;
    12. 			visit_[i] = false;
    13. 		}
    14. 		minLen[getStartId(n, value)] = INT_MIN;
    15. 		vectorint, int>>ans;
    16. 		for (int i = 0; i < n; i++) {
    17. 			int id = getId(n, visit_, minLen);
    18. 			for (int j = 0; j < n; j++) {
    19. 				if (visit_[j] && value[make_pair(id, j)] == minLen[id]) {
    20. 					ans.push_back(make_pair(id, j));
    21. 					break;
    22. 				}
    23. 			}
    24. 			visit_[id] = true;
    25. 			fresh(n, visit_, minLen, value, id);
    26. 		}
    27. 		return ans;
    28. 	}
    29. private:
    30. 	static int getStartId(int n, mapint, int>, int>& value)
    31. 	{
    32. 		int m = INT_MAX;
    33. 		int ans = 0;
    34. 		for (int i = 0; i < n; i++) {
    35. 			for (int j = 0; j < n; j++) {
    36. 				if (i != j && m > value[make_pair(i, j)]) {
    37. 					m = value[make_pair(i, j)];
    38. 					ans = i;
    39. 				}
    40. 			}
    41. 		}
    42. 		return ans;
    43. 	}
    44. 	static int getId(int n, vector<bool>& visit_, vector<int>& minLen)
    45. 	{
    46. 		int m = INT_MAX;
    47. 		int ans = 0;
    48. 		for (int i = 0; i < n; i++) {
    49. 			if (!visit_[i] && m > minLen[i]) {
    50. 				m = minLen[i];
    51. 				ans = i;
    52. 			}
    53. 		}
    54. 		return ans;
    55. 	}
    56. 	static void fresh(int n, vector<bool>& visit_, vector<int>& minLen, mapint, int>, int>& value, int id)
    57. 	{
    58. 		for (int i = 0; i < n; i++) {
    59. 			if (!visit_[i])minLen[i] = min(minLen[i], value[make_pair(i, id)]);
    60. 		}
    61. 	}
    62. };

    2，测试代码

    1. bool testPrim()//待完善
    2. {
    3. 	Prim{};
    4. 	return true;
    5. }
    6.  
    7. int main()
    8. {
    9. 	if (testPrim())cout << "test succ!";
    10. 	return 0;
    11. }

    七，有向图、单源最短路径、连通分量、拓扑排序

    1，代码

    1. template<typename T = int>
    2. struct DirectedEdge
    3. {
    4. 	DirectedEdge() {
    5. 		a = b = dist = 0;
    6. 	};
    7. 	DirectedEdge(const vector<int>&v) {
    8. 		a = v[0], b = v[1], dist = v[2];
    9. 	}
    10. 	int a;//端点a的id
    11. 	int b;//端点b的id
    12. 	T dist;//从a到b的距离
    13. };
    14. template<typename T = int>
    15. struct DirectedGraphData
    16. {
    17. public:
    18. 	vector>edges; //边集，无法表示孤立点
    19. 	mapint, int>, T>edgeMap; //边集，无法表示孤立点
    20. 	map<int, vector<int>>adjaList;//邻接表，孤立点是否出现取决于allPointFlag
    21. 	bool allPointFlag = false;//默认邻接表中不含孤立点
    22. 	int startId = 0;
    23. public:
    24.     DirectedGraphData(){
    25. 	}
    26. 	DirectedGraphData(const vector>& edges) {
    27. 		this->edges = edges;
    28. 		adjaList = directedEdgeToAdjaList(edges);
    29. 		edgeMap = directedEdgeToValueMap(edges);
    30. 	}
    31. 	DirectedGraphData(const vectorint>>& edges) { //仅限权值为整数的图
    32. 		transform(edges.begin(), edges.end(), std::back_inserter(this->edges), [](const vector<int>& v) {return DirectedEdge<int>{v}; });
    33. 		adjaList = directedEdgeToAdjaList(this->edges);
    34. 		edgeMap = directedEdgeToValueMap(this->edges);
    35. 	}
    36. 	DirectedGraphData(map<int, vector<int>>& adjaList) { //仅限没有权值的图
    37. 		this->adjaList = adjaList;
    38. 		for (auto& v : adjaList) {
    39. 			for (auto vi : v.second)edges.push_back(DirectedEdge({v.first, vi, 0}));
    40. 		}
    41. 		edgeMap = directedEdgeToValueMap(edges);
    42. 	}
    43. 	void setNumV(int n, int startId = 0) { //startId一般是0或1,可以大于1
    44. 		allPointFlag = true;
    45. 		for (int i = startId; i < startId + n; i++)adjaList[i];
    46. 		this->startId = startId;
    47. 	}
    48. 	int getNumV() const {
    49. 		return adjaList.size();
    50. 	}
    51. 	int getNumE() const {
    52. 		return edges.size();
    53. 	}
    54. private:
    55. 	//输入有向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{3}}
    56. 	static map<int, vector<int>> directedEdgeToAdjaList(const vector>& v)
    57. 	{
    58. 		map<int, vector<int>> ans;
    59. 		for (auto& vi : v) {
    60. 			ans[vi.a].push_back(vi.b);
    61. 			ans[vi.b];
    62. 		}
    63. 		return ans;
    64. 	}
    65. 	//输入有向带权边集，输出边和权的映射
    66. 	static mapint, int>, int> directedEdgeToValueMap(const vector>& v)
    67. 	{
    68. 		mapint, int>, int>m;
    69. 		for (auto& vi : v) {
    70. 			m[{vi.a, vi.b}] = vi.dist;
    71. 		}
    72. 		return m;
    73. 	}
    74. };
    75. class DirectedGraph
    76. {
    77. public:
    78. 	//构建有向图的反向图
    79. 	static map<int, vector<int>> reverseGraph(const DirectedGraphData<int> &g)
    80. 	{
    81. 		auto& m = g.adjaList;
    82. 		map<int, vector<int>> ans;
    83. 		for (auto& mi : m) {
    84. 			for (auto& k : mi.second)ans[k].push_back(mi.first);
    85. 		}
    86. 		return ans;
    87. 	}
    88. 	//求有向无环图中的最长路径长度，出参nextNode是每个点的后继,len是每个点出发的最长路径长度
    89. 	static int getLongestPath(map<int, vector<int>>& m, map<int, int>& nextNode, map<int, int>& len)
    90. 	{
    91. 		int ans = 0;
    92. 		for (auto& ai : m)ans = max(ans, dp(m, nextNode, len, ai.first));
    93. 		return ans;
    94. 	}
    95. 	//判断是否有环
    96. 	static bool hasCircle(int numCourses, map<int, vector<int>>& m)
    97. 	{
    98. 		map<int, int>visitt;//单次访问标记
    99. 		map<int, int>flag;//所有访问标记
    100. 		for (int i = 0; i < numCourses; i++)
    101. 		{
    102. 			if (flag[i])continue;
    103. 			if (!canFinish(m, i, visitt, flag))return true;
    104. 		}
    105. 		return false;
    106. 	}
    107.  
    108. private:
    109. 	static int dp(map<int, vector<int>>& m, map<int, int>& nextNode, map<int, int>& len, int id)
    110. 	{
    111. 		if (len[id])return len[id];
    112. 		len[id] = 1, nextNode[id] = -1; //无后继的则是 - 1
    113. 		for (auto k : m[id]) {
    114. 			if (len[id] < dp(m, nextNode, len, k) + 1) {
    115. 				len[id] = dp(m, nextNode, len, k) + 1;
    116. 				nextNode[id] = k;
    117. 			}
    118. 		}
    119. 		return len[id];
    120. 	}
    121. 	static bool canFinish(map<int, vector<int>>& m, int loc, map<int, int>& visitt, map<int, int>& flag) {
    122. 		if (visitt[loc] == 1)return false;
    123. 		if (flag[loc] == 1)return true;
    124. 		visitt[loc] = 1, flag[loc] = 1;
    125. 		for (int k : m[loc])if (!canFinish(m, k, visitt, flag))return false;
    126. 		visitt[loc] = 0;
    127. 		return true;
    128. 	}
    129. };
    130. class Dijskra//求最短路,适用于不存在负权值的边的图
    131. {
    132. public:
    133. 	static map<int, int> shortestPath(map<int, vector<int>>& m, mapint, int>, int>& value, int n, int src)
    134. 	{
    135. 		map<int, int>dis;
    136. 		priority_queue< Node, vector< Node>, cmp>que;
    137. 		map<int, int>visit;
    138. 		for (int i = 0; i < n; i++)dis[i] = INT_MAX;
    139. 		que.push({ src,0 });
    140. 		dis[src] = 0;
    141. 		while (!que.empty())
    142. 		{
    143. 			Node nod = que.top();
    144. 			que.pop();
    145. 			if (visit[nod.id])continue;
    146. 			visit[nod.id] = 1;
    147. 			for (auto& vi : m[nod.id]) {
    148. 				if (nod.len + value[{nod.id, vi}] < dis[vi]) {
    149. 					que.push({ vi, dis[vi] = nod.len + value[{nod.id, vi}] });
    150. 				}
    151. 			}
    152. 		}
    153. 		return dis;
    154. 	}
    155. private:
    156. 	struct Node
    157. 	{
    158. 		int id;
    159. 		int len;
    160. 	};
    161. 	class cmp
    162. 	{
    163. 	public:
    164. 		bool operator()(Node a, Node b)
    165. 		{
    166. 			return a.len > b.len;
    167. 		}
    168. 	};
    169. };
    170. class BellmanFord //求最短路,适用于不存在负权值的环的图
    171. {
    172. public:
    173. 	static map<int, int> shortestPath(const DirectedGraphData<int>& g, int src)
    174. 	{
    175. 		map<int, int>dis;
    176. 		int n = g.getNumV();
    177. 		for (int i = 0; i < n; i++)dis[i] = INT_MAX;
    178. 		dis[src] = 0;
    179. 		for (int i = 0; i < n; i++) {
    180. 			if (!refresh(g.edgeMap, dis))break;
    181. 			if (i == n - 1)return map<int, int>{}; //有负环
    182. 		}
    183. 		return dis;
    184. 	}
    185. private:
    186. 	static inline bool refresh(const mapint, int>, int>& value, map<int, int>&dis)
    187. 	{
    188. 		bool flag = false;
    189. 		auto dis2 = dis;
    190. 		for (auto& e : value) {
    191. 			if (dis2[e.first.second] > ((long long)dis[e.first.first]) + e.second) {
    192. 				dis2[e.first.second] = ((long long)dis[e.first.first]) + e.second, flag = true;
    193. 			}
    194. 		}
    195. 		dis = dis2;
    196. 		return flag;
    197. 	}
    198. };
    199. class SPFA //求最短路,适用于不存在负权值的环的图
    200. {
    201. public:
    202. 	static map<int, int> shortestPath(const DirectedGraphData<int>& g, int src)
    203. 	{
    204. 		map<int, int>dis;
    205. 		map<int, bool>inQueue;
    206. 		map<int, int>visit;
    207. 		int n = g.getNumV();
    208. 		for (int i = 0; i < n; i++)dis[i] = INT_MAX;
    209. 		dis[src] = 0;
    210. 		queue<int>q;
    211. 		q.push(src);
    212. 		visit[src]++;
    213. 		inQueue[src] = true;
    214. 		while (!q.empty()) {
    215. 			int t = q.front();
    216. 			q.pop();
    217. 			inQueue[t] = false;
    218. 			auto v = refresh(dis, t, g);
    219. 			for (auto vi : v) {
    220. 				if (inQueue[vi])continue;
    221. 				q.push(vi);
    222. 				inQueue[vi] = true;
    223. 				if (++visit[vi] >= n)return map<int, int>{};//存在负环
    224. 			}
    225. 		}
    226. 		return dis;
    227. 	}
    228. private:
    229. 	static inline vector<int> refresh(map<int, int>&dis, int t, const DirectedGraphData<int>& g)
    230. 	{
    231. 		vector<int>ans;
    232. 		auto it = g.adjaList.find(t);
    233. 		if (it == g.adjaList.end())return ans;
    234. 		long long d = dis[t];
    235. 		for (auto vi : it->second) {
    236. 			if (dis[vi] > d + g.edgeMap.at(make_pair(t, vi))) {
    237. 				dis[vi] = d + g.edgeMap.at(make_pair(t, vi));
    238. 				ans.push_back(vi);
    239. 			}
    240. 		}
    241. 		return ans;
    242. 	}
    243. };
    244. //不区分有向图和无向图的通用操作
    245. class GraphOpt
    246. {
    247. public:
    248. 	//根据点集取子图,输入邻接表，输出邻接表
    249. 	static map<int, vector<int>> getSubGraph(map<int, vector<int>>& m, vector<int>& v)
    250. 	{
    251. 		map<int, vector<int>>ans;
    252. 		map<int, int>mv;
    253. 		for (auto vi : v)mv[vi] = 1;
    254. 		for (auto vi : v) {
    255. 			for (auto mi : m[vi]) {
    256. 				if (mv[mi])ans[vi].push_back(mi);
    257. 			}
    258. 		}
    259. 		return ans;
    260. 	}
    261. };
    262. class SemiConnect
    263. {
    264. public:
    265. 	//半连通分量分割
    266. 	static vectorint>> semiConnectComponent(map<int, vector<int>>& m)
    267. 	{
    268. 		vectorint>>allans;
    269. 		map<int, int>visit;
    270. 		for (auto& mi : m) {
    271. 			int k = mi.first;
    272. 			if (visit[k])continue;
    273. 			vector<int>ans;
    274. 			DFS(m, visit, k, ans);
    275. 			allans.push_back(ans);
    276. 		}
    277. 		return allans;
    278. 	}
    279. protected:
    280. 	//DFS从k开始遍历，记录所有节点最后一次访问的顺序的反序
    281. 	static void DFS(map<int, vector<int>>& m, map<int, int>& visit, int k, vector<int>& ans)
    282. 	{
    283. 		if (visit[k])return;
    284. 		visit[k] = 1;
    285. 		for (auto i : m[k])DFS(m, visit, i, ans);
    286. 		ans.insert(ans.begin(), k);
    287. 	}
    288. };
    289. class KosarajuStrongConnect :public DirectedGraph, public GraphOpt, public SemiConnect
    290. {
    291. public:
    292. 	//Kosaraju算法，强连通分量分割
    293. 	static vectorint>> connectComponent(map<int, vector<int>>& m)
    294. 	{
    295. 		vectorint>> semi = semiConnectComponent(m);
    296. 		auto m2 = reverseGraph(m);
    297. 		vectorint>>allans;
    298. 		map<int, int>visit;
    299. 		for (auto& s : semi) {
    300. 			auto m3 = getSubGraph(m2, s);
    301. 			for (auto& k : s) {
    302. 				if (visit[k])continue;
    303. 				vector<int>ans;
    304. 				DFS(m3, visit, k, ans);
    305. 				allans.push_back(ans);
    306. 			}
    307. 		}
    308. 		return allans;
    309. 	}
    310. 	//强连通分量缩点，输入强连通分量列表，输出缩点后的邻接表
    311. 	static map<int, vector<int>> getPointGraph(vectorint>>&v, map<int, vector<int>>&m)
    312. 	{
    313. 		map<int, int>g;
    314. 		map<int, vector<int>>ans;
    315. 		for (int i = 0; i < v.size(); i++)for (auto x : v[i])g[x] = i;
    316. 		for (auto &mi : m) {
    317. 			for (auto x : mi.second)
    318. 				if (g[x] != g[mi.first])
    319. 					ans[mi.first].push_back(x);
    320. 		}
    321. 		return ans;
    322. 	}
    323. };
    324. class TarjanDoubledirect
    325. {
    326. public:
    327. 	vectorint, int>>cutb;//割边
    328. 	vector<int>cutv;//割点
    329. 	vectorint>>conv;//点双连通分量的点集
    330. 	vectorlong long>>convb;//点双连通分量的边集
    331. 	int cons = 0;//无向连通分量数目
    332. 	TarjanDoubledirect(int n, map<int, vector<int>>& m)
    333. 	{
    334. 		this->n = n;
    335. 		this->m = m;
    336. 		visit.resize(n);
    337. 		added.resize(n);
    338. 		dfn.resize(n);
    339. 		low.resize(n);
    340. 		for (int i = 0; i < n; i++)if (!visit[i]) {
    341. 			root = i;
    342. 			dfs(i);
    343. 			cons++;
    344. 		}
    345. 		FillConv();
    346. 	}
    347. private:
    348. 	void dfs(int k)
    349. 	{
    350. 		visit[k] = true;
    351. 		low[k] = dfn[k] = dfnId++;
    352. 		bool cv = false;
    353. 		int chNum = 0;
    354. 		st.push(k);
    355. 		for (auto nk : m[k]) {
    356. 			if (isBackB(nk))low[k] = min(low[k], dfn[nk]);
    357. 			if (visit[nk])continue;
    358. 			chNum++;
    359. 			sFa.push(k);
    360. 			dfs(nk);
    361. 			sFa.pop();
    362. 			low[k] = min(low[k], low[nk]);
    363. 			vector<int>conv1;
    364. 			vector<long long>convb1;
    365. 			if (low[nk] >= dfn[k]) {
    366. 				cv = true;
    367. 				for (int time = INT_MAX; time; time--) {
    368. 					if (st.top() == nk)time = 1;
    369. 					conv1.push_back(st.top());
    370. 					added[st.top()] = true;
    371. 					for (auto i : m[st.top()])if (!added[i])convb1.push_back((long long)(st.top()) * n + i);
    372. 					st.pop();
    373. 				}
    374. 				if (conv1.size() > 1) {
    375. 					conv1.push_back(k);
    376. 					conv.push_back(conv1);
    377. 					convb.push_back(convb1);
    378. 				}
    379. 			}
    380. 			if (low[nk] >= dfn[nk])cutb.push_back(make_pair(k, nk));
    381. 		}
    382. 		if ((k != root && cv && chNum > 0) || (k == root && chNum > 1))cutv.push_back(k);
    383. 	}
    384. 	bool isBackB(int nk) // 判断从k到nk是不是后向边
    385. 	{
    386. 		return visit[nk] && (sFa.empty() || nk != sFa.top());//如果st.top()是nk，则是树边，不是后向边
    387. 	}
    388. 	void FillConv()//补充由单点组成的点连通分量
    389. 	{
    390. 		map<int, int>m;
    391. 		for (auto& ci : conv) {
    392. 			for (auto& k : ci)m[k] = 1;
    393. 		}
    394. 		vector<int>conv1(1);
    395. 		for (int i = 0; i < n; i++)if (m[i] == 0) {
    396. 			conv1[0] = i;
    397. 			conv.push_back(conv1);
    398. 			convb.push_back(vector<long long>());
    399. 		}
    400. 	}
    401. 	int n;
    402. 	int dfnId = 0;
    403. 	int root;
    404. 	vector<bool>visit;//DFS访问标记
    405. 	vector<bool>added;
    406. 	vector<int>dfn;//首次访问的次序
    407. 	vector<int>low;//通过一条后向边能达到的最小dfn
    408. 	map<int, vector<int>> m;//邻接表
    409. 	stack<int>sFa;//用于判断父节点
    410. 	stack<int>st;
    411. };
    412. class TarjanStrongConnect
    413. {
    414. public:
    415. 	vectorint>>conv;//强连通分量的点集
    416. 	TarjanStrongConnect(int n, map<int, vector<int>>& m)
    417. 	{
    418. 		this->n = n;
    419. 		this->m = m;
    420. 		visit.resize(n);
    421. 		added.resize(n);
    422. 		dfn.resize(n);
    423. 		low.resize(n);
    424. 		for (int i = 0; i < n; i++)if (!visit[i]) {
    425. 			root = i;
    426. 			dfs(i);
    427. 		}
    428. 		FillConv();
    429. 	}
    430. private:
    431. 	void dfs(int k)
    432. 	{
    433. 		visit[k] = true;
    434. 		low[k] = dfn[k] = dfnId++;
    435. 		bool cv = false;
    436. 		int chNum = 0;
    437. 		st.push(k);
    438. 		for (auto nk : m[k]) {
    439. 			if (isBackB(nk))low[k] = min(low[k], dfn[nk]);
    440. 			if (visit[nk])continue;
    441. 			chNum++;
    442. 			dfs(nk);
    443. 			low[k] = min(low[k], low[nk]);
    444. 		}
    445. 		vector<int>conv1;
    446. 		vector<long long>convb1;
    447. 		if (low[k] >= dfn[k]) {
    448. 			cv = true;
    449. 			for (int time = INT_MAX; time; time--) {
    450. 				if (st.top() == k)time = 1;
    451. 				conv1.push_back(st.top());
    452. 				added[st.top()] = true;
    453. 				st.pop();
    454. 			}
    455. 			conv.push_back(conv1);
    456. 		}
    457. 	}
    458. 	bool isBackB(int nk) // 判断从k到nk是不是后向边
    459. 	{
    460. 		return visit[nk] && !added[nk];
    461. 	}
    462. 	void FillConv()//补充由单点组成的点连通分量
    463. 	{
    464. 		map<int, int>m;
    465. 		for (auto& ci : conv) {
    466. 			for (auto& k : ci)m[k] = 1;
    467. 		}
    468. 		vector<int>conv1(1);
    469. 		for (int i = 0; i < n; i++)if (m[i] == 0) {
    470. 			conv1[0] = i;
    471. 			conv.push_back(conv1);
    472. 		}
    473. 	}
    474. 	int n;
    475. 	int dfnId = 0;
    476. 	int root;
    477. 	vector<bool>visit;//DFS访问标记
    478. 	vector<bool>added;
    479. 	vector<int>dfn;//首次访问的次序
    480. 	vector<int>low;//通过一条后向边能达到的最小dfn
    481. 	map<int, vector<int>> m;//邻接表
    482. 	stack<int>st;
    483. };
    484. //有向图拓扑排序
    485. class DirectedTopoSort:public KosarajuStrongConnect
    486. {
    487. public:
    488. 	//有向无环图拓扑排序，输入n=3，g.edges={{0,1}{0,2}{1,2}}, 输出{0,1,2}，有环则输出为空
    489. 	static vector<int> topoSortNoCircle(int n, DirectedGraphData<int>& g)
    490. 	{
    491. 		auto& v = g.edges;
    492. 		priority_queue<int, vector<int>, greater<int>> q;
    493. 		map<int, int>m;
    494. 		for (auto &vi : v)m[vi.b]++;
    495. 		for (int i = 0; i < n; i++)if (m[i] == 0)q.push(i);
    496. 		vector<int>ans;
    497. 		auto &mv = g.adjaList;
    498. 		while (!q.empty()) {
    499. 			int k = q.top();
    500. 			q.pop();
    501. 			ans.push_back(k);
    502. 			for (auto i : mv[k]) {
    503. 				m[i]--;
    504. 				if (m[i] == 0)q.push(i);
    505. 			}
    506. 		}
    507. 		return ans.size() == n ? ans : vector<int>{};
    508. 	}
    509. 	//有向图拓扑排序
    510. 	static vectorint>> topoSort(DirectedGraphData<int>& g)
    511. 	{
    512. 		vectorint>> con = connectComponent(g.adjaList);
    513. 		map<int, vector<int>> pointGraph = getPointGraph(con, g.adjaList);
    514. 		DirectedGraphData<int>ga(pointGraph);
    515. 		vector<int> vp = topoSortNoCircle(con.size(), ga);
    516. 		vectorint>>ans;
    517. 		for (auto id : vp)ans.push_back(con[id]);
    518. 		return ans;
    519. 	}
    520. };

    2，测试代码

    1. bool testDirectedGraph()//待完善
    2. {
    3. 	DirectedGraph{};
    4. 	return true;
    5. }
    6. bool testDijskra()//待完善
    7. {
    8. 	map<int, vector<int>> m;
    9. 	mapint, int>, int> value;
    10. 	int n = 1;
    11. 	DijskraShortestPath(m, value, n, 0);
    12. 	return true;
    13. }
    14. bool testBellmanFord()//待完善
    15. {
    16. 	return true;
    17. }
    18. bool testGraphOpt()//待完善
    19. {
    20. 	GraphOpt{};
    21. 	return true;
    22. }
    23. bool testConnect()//待完善
    24. {
    25. 	SemiConnect{};
    26. 	KosarajuStrongConnect{};
    27. 	int n = 1;
    28. 	map<int, vector<int>> m;
    29. 	TarjanDoubledirect{ n,m };
    30. 	TarjanStrongConnect{ n,m };
    31. 	return true;
    32. }
    33. bool testTopoSort() //待完善
    34. {
    35. 	map<int, vector<int>>m;
    36. 	m[1].push_back(2);
    37. 	m[2].push_back(3);
    38. 	m[3].push_back(1);
    39. 	m[3].push_back(4);
    40. 	m[4].push_back(5);
    41. 	m[5].push_back(6);
    42. 	m[6].push_back(4);
    43. 	m[5].push_back(7);
    44. 	DirectedGraphData<int>g(m);
    45. 	auto ans = DirectedTopoSort::topoSort(g);
    46. 	return true;
    47. }
    48. bool test5()
    49. {
    50. 	return testDirectedGraph() && testDijskra() && testBellmanFord() && testGraphOpt() && testConnect() && testTopoSort();
    51. }
    52.  
    53. int main()
    54. {
    55. 	if (test5())cout << "test succ!";
    56. 	return 0;
    57. }

    八，网格图、回路链路、路径重建

    1，代码

    1. class GridGraph
    2. {
    3. public:
    4. 	GridGraph(int row, int col)
    5. 	{
    6. 		this->row = row;
    7. 		this->col = col;
    8. 		initD4D8();
    9. 	}
    10. 	int gridId(int r, int c) //阅读顺序的id,先给col赋值再调用
    11. 	{
    12. 		return r * col + c;
    13. 	}
    14. 	vector<int> getNeighbor4(int k)//获得四邻居的id
    15. 	{
    16. 		vector<int>ans;
    17. 		for (int i = 0; i < 4; i++) {
    18. 			if (inBoard(k / col + dx4[i], k % col + dy4[i]))ans.push_back(k + d4[i]);
    19. 		}
    20. 		return ans;
    21. 	}
    22. 	vector<int> getNeighbor8(int k)//获得八邻居的id
    23. 	{
    24. 		vector<int>ans;
    25. 		for (int i = 0; i < 8; i++) {
    26. 			if (inBoard(k / col + dx8[i], k % col + dy8[i]))ans.push_back(k + d8[i]);
    27. 		}
    28. 		return ans;
    29. 	}
    30. private:
    31. 	int row;
    32. 	int col;
    33. 	//二维坐标系的邻居偏移量
    34. 	const vector<int> dx4{ 0,0,1,-1 };
    35. 	const vector<int> dy4{ 1,-1,0,0 };
    36. 	const vector<int> dx8{ 0,0,1,-1,1,1,-1,-1 };
    37. 	const vector<int> dy8{ 1,-1,0,0 ,1,-1,1,-1 };
    38. 	//一维id坐标系的邻居偏移量
    39. 	vector<int> d4;
    40. 	vector<int> d8;
    41. private:
    42. 	inline void initD4D8()
    43. 	{
    44. 		for (int i = 0; i < 4; i++)d4.push_back(gridId(dx4[i], dy4[i]));
    45. 		for (int i = 0; i < 8; i++)d8.push_back(gridId(dx8[i], dy8[i]));
    46. 	}
    47. 	inline bool inBoard(int r, int c)
    48. 	{
    49. 		return r >= 0 && r < row&& c >= 0 && c < col;
    50. 	}
    51. 	inline bool inBoard(int id)
    52. 	{
    53. 		return id >= 0 && inBoard(id / col, id % col);
    54. 	}
    55. };
    56. class Hierholzer {
    57. public:
    58. 	stack<int>euler;//欧拉回路或链路,栈顶是起点
    59. 	Hierholzer(int n, map<int, vector<int>>& m, int type, int start = 0)//type=0是无向图 1是有向图
    60. 	{
    61. 		this->n = n;
    62. 		this->m = m;
    63. 		this->type = type;
    64. 		dfs(GetStartPoint(start));
    65. 	}
    66. private:
    67. 	int GetStartPoint(int start)//链路是唯一起点，回路是指定起点
    68. 	{
    69. 		if (type == 0) {
    70. 			for (auto& mi : m) {
    71. 				if (mi.second.size() % 2)return mi.first;
    72. 				for (auto nk : mi.second)num[id(mi.first, nk)]++;
    73. 			}
    74. 			for (auto& ni : num)ni.second /= 2;
    75. 		}
    76. 		else {
    77. 			map<int, int>m2;
    78. 			for (auto& mi : m)for (auto nk : mi.second)m2[nk]++, num[id(mi.first, nk)]++;
    79. 			for (auto& mi : m)if (mi.second.size() > m2[mi.first])return mi.first;
    80. 		}
    81. 		return start;
    82. 	}
    83. 	void dfs(int k)
    84. 	{
    85. 		while (true) {
    86. 			while (mid[k] < m[k].size()) {
    87. 				if (num[id(k, m[k][mid[k]])]-- <= 0)mid[k]++;
    88. 				else sdfs.push(k), k = m[k][mid[k]];
    89. 			}
    90. 			euler.push(k);
    91. 			if (sdfs.empty()) return;
    92. 			k = sdfs.top(), sdfs.pop();
    93. 		}
    94. 	}
    95. 	inline long long id(int a, int b)
    96. 	{
    97. 		if (type == 0 && a > b)a ^= b ^= a ^= b;
    98. 		return (long long)a * n + b;
    99. 	}
    100. 	int n;
    101. 	int type;
    102. 	stack<int>sdfs;
    103. 	map<int, vector<int>> m;//邻接表
    104. 	map<int, int>mid;
    105. 	map<long long, int>num;//支持多重边
    106. };
    107. class Hamilton
    108. {
    109. public:
    110. 	stack<int> hami;//哈密顿链路
    111. 	Hamilton(int n, map<int, vector<int>>& m, int type)//type=0是无向图 1是有向图
    112. 	{
    113. 		this->n = n;
    114. 		this->m = m;
    115. 		this->type = type;
    116. 		for (int i = 0; i < n; i++)dfs(i);
    117. 	}
    118. private:
    119. 	bool dfs(int k)
    120. 	{
    121. 		s.push(k);
    122. 		if (s.size() == n) {
    123. 			hami = s;
    124. 			return true;
    125. 		}
    126. 		for (auto nk : m[k]) {
    127. 			if (visit[k])continue;
    128. 			visit[k] = 1;
    129. 			if (dfs(nk))return true;
    130. 			visit[k] = 0;
    131. 		}
    132. 		s.pop();
    133. 		return false;
    134. 	}
    135. 	int n;
    136. 	int type;
    137. 	map<int, vector<int>> m;//邻接表
    138. 	map<int, int>visit;
    139. 	stack<int>s;
    140. };
    141. class ReBuild
    142. {
    143. public:
    144. 	stack<int> ans;
    145. 	ReBuild(map<int, int>& dis, map<int, vector<int>>& m, int col, int s, int e)
    146. 	{
    147. 		this->e = e;
    148. 		this->col = col;
    149. 		ans.push(e);
    150. 		dfs(dis, m, s);
    151. 	}
    152. private:
    153. 	bool dfs(map<int, int>& dis, map<int, vector<int>>& m, int k)
    154. 	{
    155. 		if (k == e)return true;
    156. 		for (int nex : m[k]) {
    157. 			if (dis[nex] == dis[k] + len(k, nex) && dfs(dis, m, nex)) {
    158. 				ans.push(k);
    159. 				return true;
    160. 			}
    161. 		}
    162. 		return false;
    163. 	}
    164. 	int len(int s, int e)
    165. 	{
    166. 		if (s / col == e / col)return abs(s - e);
    167. 		return abs(s - e) / col;
    168. 	}
    169. 	int col;
    170. 	int e;
    171. };

    2，测试代码

    1. bool testGridGraph()//待完善
    2. {
    3. 	GridGraph{ 0, 0 };
    4. 	return true;
    5. }
    6.  
    7. bool testHierholzerAndHamilton()//待完善
    8. {
    9. 	map<int, vector<int>> m;
    10. 	mapint, int>, int> value;
    11. 	int n = 1;
    12. 	Hierholzer{ n,m,0,0 };
    13. 	Hamilton{ n,m,0 };
    14. 	return true;
    15. }
    16. bool testReBuild()//待完善
    17. {
    18. 	map<int, vector<int>> m;
    19. 	map<int, int> dis;
    20. 	ReBuild{ dis,m,0,0,0 };
    21. 	return true;
    22. }
    23. bool test6()
    24. {
    25. 	return testGridGraph() && testHierholzerAndHamilton() && testReBuild();
    26. }
    27.  
    28. int main()
    29. {
    30. 	if (test6())cout << "test succ!";
    31. 	return 0;
    32. }

  • 相关阅读:
    什么是redis，redis能做什么，redis的应用场景
    C++ Reference: Standard C++ Library reference: Containers: array: array: end
    CMT2380F32模块开发17-ADC例程
    6.19-MyBatis源码—体系介绍和配置文件解析源码剖析
    百度一面：谈谈 @Transactional 的原理和坑
    LQ0159 无穷分数【计算精度】
    Redis数据类型
    LeetCode每日一题(1573. Number of Ways to Split a String)
    中国金控盐碱地水稻 国稻种芯-林裕豪：粮食安全两会热点
    MongoDB数据库一篇全解
  • 原文地址：https://blog.csdn.net/nameofcsdn/article/details/132857972