Description
Monocarp有一棵树,可是他已经忘记了它的形态。但是他有这棵树的$bfs$序,并且对于每一个节点,$bfs$都会按照升序遍历它的子节点。现在给出这个$bfs$序,求出这棵树的最小深度。
Solution
先观察一下这个BFS序的性质
因为它给的BFS是按照升序访问子节点的,那么对于每个点后面出现的节点,如果它后面的点比他的编号还小,说明要新开一层,否则就可以一直堆在一层
举个例子:1 4 3 2
1
已经确定是根,那么1
的第一个子节点就是4
,观察到4
是目前1
的子节点中编号最小的,如果我们要把2
也弄成1
的子节点,那么按照BFS序,2
应该在4
前面出现,所以这样是不合法的,说明2
要新开一层成为4
的子节点
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 2e5 + 5;
int T, n, ans;
int a[SIZE], dep[SIZE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void bfs()
{
std::queue < int > q;
memset(dep, 0, sizeof(dep));
q.push(1);
int pos = 2;
while (!q.empty()) {
int u = q.front();
q.pop();
ans = std::max(ans, dep[u]);
int lst = pos;
if (pos > n) break;
while (a[pos + 1] > a[pos] && pos < n) ++ pos;
for (int i = lst; i <= pos; ++ i) {
dep[a[i]] = dep[u] + 1;
q.push(a[i]);
}
++ pos;
}
}
int main()
{
T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
ans = 0;
bfs();
for (int i = 1; i <= n; ++ i) ans = std::max(ans, dep[i]);
printf("%d\n", ans);
}
return 0;
}