【栈模拟DFS】ZOJ_2615_Cells
Scientists are conducting research on the behavior of a newly discovered Agamic Cellular Microbe. This
special kind of microbe is capable of massively reproducing by itself in a short time. The lifetime of an
ACM consists of three phases:
- The infancy phase, which starts from its birth and lasts for approximately several seconds;
- The multiplication phase, in which one ACM can procreate up to 100 offspring in only several
milliseconds; - The mature phase, in which it remains inactive for the rest of its life.
At the beginning of the experiment, a newborn, single cell of ACM, is put into a suitable cir-
cumstance for its production. This cell, numbered as 0, starts to multiply and its descendants are
numbered, starting from 1, according to their positions in the family hierarchy. During the experiment
special equipment is used to record the numbers of the offspring generated by each of the ACM's. The
experiment is stopped after a certain time period.
Paste_Image.png
The family tree of ACM's in the _rst case of sample input
Your task is to help the scientists to determine whether one ACM is an ancestor of another.
Input
Standard input will contain multiple test cases. The _rst line of the input is a single integer T (1 _
T _ 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.
Each test case starts with a single integer N (1 _ N _ 300; 000) which is the number of ACM's
that have their descendants recorded. The following N integers (not necessarily on a same line), Ci
(0 _ i < N; 0 _ Ci _ 100), give the number of offspring of the i-th ACM. The next line contains an
integer M (1 _ M _ 1; 000; 000) which is the number of queries. M lines follow, each contains two
integers a and b, querying whether the a-th ACM is an ancestor of the b-th ACM.
The total number of ACM's may be greater than N, but would never exceed 20,000,000.
Output
Results should be directed to standard output. Start each case with `Case #:' on a single line, where
# is the case number starting from 1. Two consecutive cases should be separated by a single blank
line. No blank line should be produced after the last test case.
For each query, print either 'Yes' or 'No' on a single line, which is the answer to the query.
Sample Input
2
6
3 2 1 1 0 2
5
0 1
2 4
3 5
1 8
6 9
5
2 0 3 0 1
4
2 6
1 6
2 3
3 5
Sample Output
Case 1:
Yes
No
No
Yes
No
Case 2:
Yes
No
Yes
No
题意：
给一颗树，求两个节点是否存在父子关系。
思路：
由于数据量非常大，直接深搜绝对超时，最坏的情况下所有节点形成一条链，遍历一次就会超时。
这里使用栈模拟DFS过程，并记录每一个节点的进出栈时间。对于某一对存在父子关系的节点，一定有：父节点先子节点进栈，子节点先父节点出栈。模拟一遍DFS，判断即可。
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 300000;
const int maxm = 20000000;
int buf[maxn + 10];
int child[maxn + 10];
int token[maxn + 10]; // 判断当前的子节点
struct Node {
int in;
int out;
}node[maxm + 10];
int st[maxm + 10]; // 数组模拟栈
int top;
void dfs(int n) {
memset(token, 0, sizeof(token));
int count = 0;
top = 0;
st[top] = 0; // 根节点入栈
int cur;
while (true) {
// 大于等于n一定没有子节点，直接出栈
if (st[top] >= n) {
node[st[top]].out = count++;
--top;
}
cur = child[st[top]] + token[st[top]];
// 判断是否遍历结束
if (token[st[top]] == buf[st[top]] && top == 0) {
node[st[top]].out = count;
break;
}
// 判断当前栈顶元素的子节点是否遍历结束，出栈
else if (token[st[top]] == buf[st[top]]) {
node[st[top]].out = count++;
--top;
}
// 入栈
else {
++token[st[top]];
st[++top] = cur;
node[st[top]].in = count++;
}
}
return;
}
int main() {
int T;
scanf("%d", &T);
int n, m, a, b;
for (int tt = 1; tt <= T; ++tt) {
if (tt != 1)
printf("\n");
int num = 1;
printf("Case %d:\n", tt);
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", buf + i);
child[i] = num; // 记录起始儿子的编号
num += buf[i];
}
dfs(n);
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
scanf("%d%d", &a, &b);
if (a >= b || a >= n || node[a].in>node[b].in || node[a].out < node[b].out)
printf("No\n");
else
printf("Yes\n");
}
}
return 0;
}
