正文
♦时间复杂度:\(\mathcal{O}(n)\)
思维题,不需要建树。
设数组 \(a\) 记录每一个节点是否尊重它的父节点,数组 \(b\) 记录是否有节点尊重它,特别的,叶子节点必然不被尊重。
对于每次的输入数据 \(x,y\)。若 \(y\) 等于 1(即不尊重它的父节点),那 \(a_i \leftarrow 1\);若 \(y\) 等于 0,那 \(b_a\leftarrow 1\),最后遍历一遍,如果 \(a_i=1,b_i\ne 1\),那么代表这个节点既不尊重它的父节点,也没有子节点尊重它,输出。
代码:
#include<bits/stdc++.h>
using namespace std;
int n;
pair<bool,bool> a[(int)1e5+5];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int f,b;
cin>>f>>b;
if(b==0)
a[f==-1?0:f].second=true;
else a[i].first=true;
}
bool flag=true;
for(int i=1;i<=n;i++){
if(a[i].first and !a[i].second){
flag=false;
cout<<i<<' ';
}
}
if(flag) cout<<-1;
}
洛谷提交记录,华丽结束。
后附
日志
v1.0 on 2022.10.01: 发布
标签:1143,int,题解,CodeForces,尊重,true,节点 From: https://www.cnblogs.com/wanguan/p/16816905.html