【CF】【补题】C. Queen
C. Queen
删除对父节点不敬和全体子节点都为不孝结点的结点(自身被染色和全体子节点都被染色)(将不孝的特性看成是染上了色)
- 条件一:自身被染色。
- 条件二:全体子节点都被染色,对立情况全体子节点存在一个子节点不被染色。
- col数组用来标记,0代表不染,1代表染色
- down数组,用来记录子节点是否存在没有被染色的情况。
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
using namespace std;
const int N = 1E5+10;
int fa[N],col[N],down[N];
int main()
{
int n;
cin>>n;
repd(i,1,n)
{
cin>>fa[i]>>col[i];
if(fa[i]!=-1)
if(col[i]==0)
down[ fa[i] ]=1;
}
bool flag=1;
repd(i,1,n)
if( fa[i]!=-1&&col[ i ]==1&&down[ i ]==0)
flag=0,cout<<i<<" ";
if(flag) cout<<-1;
return 0;
}
- 渴望变强,不坑队友