洛屿的小站

什么是拓扑排序？ 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件： 每个顶点出现且只出现一次 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说 拓扑排序有什么用？ 它可以用来解决形如： 有n个任务需要完成，每个任务有一个耗时和一个前置任务列表，前置任务完成后才能开始当前任务。求完成所有任务的最短时间 这样具有依赖关系的问题 拓扑排序的实现 实现拓扑排序的关键就是维护一个入度为0的顶点的集合 Eg：P1113 杂务 题目描述 John的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有 ...

邻接矩阵实现 12345678910111213141516171819#define MAXN 10001int G[MAXN][MAXN], Nv, Ne;void BuildG() { int u, v, w; cin >> Nv; /*CreateGraph*/ for (int i = 0; i < Nv; i++) { for (int j = 0; j < Nv; j++) { G[i][j] = 0; } } cin >> Ne; for (int i = 0; i < Ne; i++) { cin >> u >> v >> w; /*InsertEdge*/ G[u][v] = w; G[v][u] = w;//针对无向图，双向建边 }}

[TOC] CAD是先设置相关样式，后绘制 命令 MENUBAR(菜单模式) 0 非标准菜单模式 1 标准菜单模式 GRID(辅助栅格) 显示/不显示 开(ON) 关(OFF) 捕捉(S) 主(M) 自适应(D) 界限(L) 跟随(F) 纵横向间距(A) OP(界面设置) 界面设置 再次按下回车可以重复运行上次的指令 CTRL+o(全屏) QS(快速保存) LA(图层命令) 图层命令 Z(缩放) 绘制相关 L(直线) PL(多段线) > 注意 **相对坐标** REC(矩形) > 参数： > > E （完全显示） LW(线宽) SPL(曲线) 完成闭合曲线后，输入c（闭合） X 将一条线段分为两条 O(偏移命令) 按键后输入偏移值 U U == ctrl+z TR(修剪) 按键后按T，选择剪切边，回车，再次选择，被选择线与剪切边间的线将被剪切 CO(copy) 选完后回车 选择基准点，选完后要求选新的基准点 文字相关 MT(多行文字) DT(单行文字) ST(文字样式) DDEDIT(文字编辑) B(块定义) BED ...

[TOC] 性质 二叉搜索树本质上还是一棵二叉树，其满足以下性质（习惯性定义为）： 非空左子树的所有键值小于其根结点的键值 非空右子树的所有键值大于其根结点的键值 左右子树都是二叉搜索树 基本函数 1234567891011121314//从二叉搜索树BST中查找x，返回结点地址Poi Find(ElementType x, BinTree BST);//从二叉搜索树BST中查找最小元素的结点地址Poi FindMin(BinTree BST);//从二叉搜索树BST中查找最大元素结点地址Poi FindMax(BinTree BST);//向二叉搜索树BST插入值为x的结点BinTree Insert(ElementType x, BinTree BST);//向二叉搜索树BST删除值为x的结点BinTree Delete(ElementType x, BinTree BST); Find 12345678910111213BiNode* BiSearchTree::Find(int x, BiNode* BST){ if (!BST) return nullptr; ...

前序中序转后序 输入#1 12ABEDFCHGCBADEFGH 输出#1 1AEFDBHGC 针对二叉树的 前序遍历，根->左->右 中序遍历，左->根->右 这两个的特性 我们可以尝试凭借前序遍历的根结点（叶子结点也可以看错左右儿子为空的根）将中序遍历的左右根依次拆分成左右两块，针对左右两块再次递归操作 12345678910111213141516171819void _find(string InOrderStr, string PreOrderStr){ if (PreOrderStr.empty())return;//针对前序遍历序列（拆分出的序列的）的根结点访问结束 char root = PreOrderStr[0]; PreOrderStr.erase(PreOrderStr.begin());//根结点取出，作为拆分标识 int rootidx = InOrderStr.find(root); string leftIn = InOrderStr.substr(0,rootidx); ...

关于二叉树的同构 一种可行的方法(基于数组的二叉树) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105struct ArrTree { char data; int left; int right;}A1T[100], A2T[100];//bool check[100];//////////////////////////////////////////////////////////////////////////////////构建函数，基于数组的二叉树//////////////////////////*构建输入的例子：可以从根结点开始8A 1 2B 3 4C 5 -D - -E 6 -G ...

先序遍历 根->左子树->右子树 1234567void BiTree::PreOrder(BiNode* B) { if (B) { cout << B->data << endl; PreOrder(B->left); PreOrder(B->right); }} 中序遍历 左子树->根->右子树 1234567void BiTree::InOrder(BiNode* B) { if (B) { PreOrder(B->left); cout << B->data << endl; PreOrder(B->right); }} 后序遍历 左子树->右子树->根 1234567void BiTree::PostOrder(BiNode* B) { if (B) { PreOrder(B->left); PreOrder(B->r ...

链表实现 stDo.webp) 图中右下角的样式不统一，若统一为3项，则有大量空间浪费，不妨如此这般 左侧结点存储儿子，右侧结点存储兄弟 这样的表示方式为：二叉树

帮助群友♂♂(AC)，就是帮助自己 单调栈 单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大（一般） 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小 （我们只会用到单调栈的一端） E.g: 单调递增栈加入数据：：：堆栈实现（栈顶为最大值） 1234567891011121314151617181920stack<int> st;//栈顶为最大值void _add(const int& x) { if (st.empty() || st.top() > x){ st.push(x); } else{ stack<int> tmp; while (!st.empty() && st.top() < x) { tmp.push(st.top()); st.pop(); } st.push(x); while (!tmp.empty()) { st.push(tmp.top()); tmp.pop();  ...

树(Tree) n(n≥0)个结点构成的有限集合 n=0时，称为空树 对于任意一颗非空树，它具有以下性质： 树中有一个称为"根(root)"的特殊节点，用root表示 其余结点可分为m(m>0)个互不相交的有限集$T_1$ $T_2$…$T_m$，其中每个集合本身又是一棵树。称为原来树的" 子树(SubTree)" 子树不相交 除根节点外，每个结点有且仅有一个父结点 一棵N个结点的树有N-1条边 （树是保证所有结点连通的一种最小连通方式之一） 相关术语 结点的度 ：结点的子树个数 树的度：树的所有结点中最大的度数 叶结点：度为0的点 父结点：有子树的结点是其子树的根结点的父结点 子结点：若A结点是B结点的父结点，则称B结点是A结点的子结点 兄弟结点：具有同一父结点的各结点彼此是兄弟结点 路径和路径长度：从结点$n_1$到$n_k$的路径为一个结点序列$n_1$，$n_2$，…，$n_k$，$n_i$是$n_i+1$的父结点。路径所包含边的个数为路径的长度 祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个 ...