题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
const int M = 1.6e7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, rt, k[N + 5];
int son[N + 5][5];
int fr[N + 5];
int ans[N + 5], cnt;

void dfs(int x, int fa) {
	fr[x] = n + 1;
	if (k[x] <= 2) {
		fr[x] = x;
	}
	for (int i = 0; i < k[x]; i++) {
		int y = son[x][i];
		if (y == fa) {
			continue;
		}
		dfs(y, x);
		fr[x] = min(fr[x], fr[y]);
	}
}

void dfs2(int x, int fa) {
	int tmp[2], tot = 0;
	for (int i = 0; i < k[x]; i++) {
		if (son[x][i] == fa) {
			continue;
		}
		tmp[tot++] = son[x][i];
	}
	if (tot == 0) {
		ans[++cnt] = x;
	} else if (tot == 1) {
		if (x < fr[tmp[0]]) {
			ans[++cnt] = x;
			dfs2(tmp[0], x);
		} else {
			dfs2(tmp[0], x);
			ans[++cnt] = x;
		}
	} else {
		if (fr[tmp[0]] > fr[tmp[1]]) {
			swap(tmp[0], tmp[1]);
		}
		dfs2(tmp[0], x);
		ans[++cnt] = x;
		dfs2(tmp[1], x);
	}
}

void dfs1(int x, int fa) {
	ans[++cnt] = x;
	int tmp[2], tot = 0;
	for (int i = 0; i < k[x]; i++) {
		if (son[x][i] == fa) {
			continue;
		}
		tmp[tot++] = son[x][i];
	}
	if (tot == 1) {
		if (fr[tmp[0]] < tmp[0]) {
			dfs2(tmp[0], x);
		} else {
			dfs1(tmp[0], x);
		}
	} else if (tot == 2) {
		if (fr[tmp[0]] > fr[tmp[1]]) {
			swap(tmp[0], tmp[1]);
		}
		dfs2(tmp[0], x);
		dfs1(tmp[1], x);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> k[i];
		for (int j = 0; j < k[i]; j++) {
			cin >> son[i][j];
		}
		if (k[i] <= 2 && !rt) {
			rt = i;
		}
	}
	dfs(rt, 0);
	dfs1(rt, 0);
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
    return 0;
}