【华为OD机试】删除目录

华为OD机试】删除目录"/>

【华为OD机试】删除目录

某文件系统中有N个目录，每个目录都一个独一无二的ID。每个目录只有一个父目录，但每个父目录下可以有零个或者多个子目录，目录结构呈树状结构。假设，根目录的ID为0，且根目录没有父目录，其他所有目录的ID用唯一的正整数表示，并统一编号。
现给定目录ID和其父目录ID的对应父子关系表[子目录ID，父目录ID]，以及一个待删除的目录ID，请计算并返回一个ID序列，表示因为删除指定目录后剩下的所有目录，返回的ID序列以递增序输出。
注意:
1、被删除的目录或文件编号一定在输入的ID序列中
2、当一个目录删除时，它所有的子目录都会被删除
输入描述
输入的第一行为父子关系表的长度m;接下来的行为m个父子关系对;最后-
行为待删除的ID。序列中的元素以空格分割，参见样例。
输出描述
输出一个序列，表示因为删除指定目录后，剩余的目录ID.
例1

输入

5
8 6
10 8
6 0
20 8
2 6
8

输出

2 6

说明
目录结构如下所示

    6
  /    \
2      8
      /    \
    10   20

删除目录8，同时它的子目录10也被删除，剩余2和6两个目录

思路：

刚参与的机试，二星题反而比一星的简单，直接上结构体记录节点、父节点和删除标记，用搜索的方式递归往下删除

代码：

#include<bits/stdc++.h>
using namespace std;struct ac {int num;int fa;int del;
} a[1005];bool cmp(ac a, ac b) {return a.num < b.num;
}void find(int n, int x) {for (int i = 0; i < n; i++) {if (a[i].del)continue;if (a[i].num == x || a[i].fa == x) {
//			cout << "---del:" << x << " " << a[i].num << " " << a[i].fa << endl;a[i].del = 1;find(n, a[i].num);}}return;
}int main() {int n, i, delNum;cin >> n;for (i = 0; i < n; i++) {cin >> a[i].num >> a[i].fa;a[i].del = 0;}cin >> delNum;find(n, delNum);
//	for (i = 0; i < n; i++) {
//		cout << a[i].num << " " << a[i].fa << " " << a[i].del << endl;
//	}sort(a, a + n, cmp);for (i = 0; i < n; i++) {if (a[i].del != 1) {cout << a[i].num << " ";}}return 0;
}