Codeforces Round #549 (Div. 2) C. Queen

C. Queen

https://codeforces.com/problemset/problem/1143/C

부모 노드를 respect하지 않고, 자식 노드도 나를 respect하지 않으면 해당 노드를 없앤다.

dfs를 root부터 돌면서, 위 조건을 충족하는 노드를 찾으면 된다.

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
 
vector<int> ans, vc[N];
int res[N];
int n, root, in ,respect;
 
bool dfs(int v) {
    bool on = false;
    for (int i = 0; i < vc[v].size(); i++) {
        if (dfs(vc[v][i])) on = true;
    }
 
    if (!on && res[v] == 0) ans.push_back(v);
    
    if (res[v] > 0) return true;
    else return false;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> in >> respect;
        if (in == -1) root = i;
        else {
            vc[in].push_back(i);
        }
        if (respect == 0) res[i] = 1;
    }
 
    dfs(root);
 
    if (ans.size() > 0) {
        sort(ans.begin(), ans.end());
        for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
    }
    else cout << -1;
 
    return 0;
}