欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

CodeforcesRound#549C.Queen

时间:2023-06-03

题目大意:给定一棵n个结点的树,每个点输入p和c,其中p代表第i个结点的父亲结点,c为0或1,1表示结点i不尊重他的父亲,0表示尊重他的父亲。请将这样的结点按照从小到大的顺序进行输出:i不尊重他的父亲且他的所有儿子都不尊重他。

题解:这题其实很简单,我们可以开两个数组resp和berp分别表示结点i是否尊重他的父亲以及结点i是否受他的儿子尊重,然后dfs进行搜索,将符合条件的点记录并且输出。

#includeusing namespace std;const int maxn = 1e5 + 10;vectorg[maxn];int resp[maxn], berp[maxn];int ans[maxn];int cnt = 0;void dfs(int x){if (g[x].size() == 0){if (resp[x] == 1)ans[cnt++] = x;return;}if (resp[x] == 1 && berp[x] == 0){ans[cnt++] = x;}for (int i = 0; i < g[x].size(); i++){dfs(g[x][i]);}}int main(){int n;cin >> n;int p, c;int root = 0;for (int i = 1; i <= n; i++){cin >> p >> resp[i];if(resp[i]==0)berp[p] = 1;g[p].push_back(i);if (p == -1)root = i;}cnt = 0;dfs(root);sort(ans, ans + cnt);for (int i = 0; i < cnt; i++)cout << ans[i] << " ";if (cnt == 0)cout << -1;}

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。