第一行输入两个整数 n 和 m,表示顶点数和边数。接下来 m 行,每行输入两个整数 x 和 y,表示一条从 x 连向 y 的无向边。之后输入一个整数 k,表示深度优先搜索的起点。注意顶点是从 0 开始编号的哦。输入完成后会将遍历结果输出。
冗余关系
蒜头最近在沉迷小说,尤其是人物关系复杂的言情小说。它看到的人物关系描述得很的麻烦的时候觉得非常蒜疼,尤其是人物关系里有冗余的时候。什么是冗余关系呢?
这篇小说里有n句描述人物关系的句子,描述了n个人的关系。
每条句子的定义是这样的:
X<->Y 它的意思是:X认识Y,Y也认识X->
我们认为小说中的人物关系是具有传递性的,假如A认识B,B认识C,则A也认识C。
冗余关系的定义:就是即使没有这条人物关系,原来的人物之间的所有关系也照样成立。
比如:
小说中已经提到了A认识B,B也认识C。在此之后再讲A认识C就是一个冗余的关系。
小蒜头想求出一共有多少条冗余关系,你能帮帮它吗?也许并查集能帮上忙哦。
LIS(最长上升子序列)
最长上升子序列 (Longest Increasing Subsequence, 常简称为 LIS) 是动态规划解决的一个经典问题。
我们先讲一下子序列是什么。一个数组的子序列就是从里面选出一些元素,并将他们保持原有的先后顺序排列。比如[1, 2, 3, 4, 5]
的子序列有[1, 3, 5]
、[3, 4]
,而[1, 5, 3]
则不是这个数组的子序列。
这里多介绍一下,还有一个容易与子序列混淆的概念:子串。子串是指从一个数组中选出连续的一个或多个元素,并且保持他们原有的顺序。子串一定是子序列,比如前面的子序列[3, 4]
就是子串,但[1, 3, 5]
不是子串,因为这三个元素在原数组中并不是连续的。
一句话总结他们的区别,就是子序列可以不连续,而子串必须连续。
上升子序列是指子序列Ai中满足 A1 < A2 < … < An,也就是后面的元素一定比前面的元素大,比如(1, 3, 5)是上升子序列,(1, 3, 3)和(1, 4, 3)都不是。现在来跟我一起解决最长上升子序列的问题吧!(o・・o)/
动归之数塔
上面这张图是一个数塔问题的例子。每次从顶部元素,就是上图中的9出发,每次可以走到下面相邻的两个节点,比如从9往下相邻的是12和15,6往下相邻的是18和9。找到一条从顶部到底部的路径,使得路径上的数值和最大。
一个直观的贪心策略是每次向下走都选择较大的那一个,得到的一个解是9+15+8+9+10=51,然而我们发现最优的解是9+12+10+18+10=59,也就是说这道题并不适合贪心策略。
接下来我们把问题分解,假如知道从顶点到每个点的最优解的话,最终答案也就能够得出了。假设第i行第j个元素为止的最优解为f[i][j],可以想到f[i][j]只和f[i-1][j]和f[i-1]j-1有关。也就是说第i行的解只会跟第i-1行的一个或两个元素有关。
QuickSort(快速排序)
1 | #include <cstdio> |
链表操作
1 | #include<iostream> |