Codigos/1143C.cpp at master · tfarnecim/Codigos · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

vector <int> grafo[200000];
bool mark[200000];
int nivel[200000];
bool passou[200000];

void bfs(int root){

	queue <int> fila;

	fila.push(root);
	passou[root] = true;
	nivel[root] = 0;

	while(!fila.empty()){

		int v = fila.front();
		fila.pop();

		for(int i=0;i<grafo[v].size();i++){

			int adj = grafo[v][i];

			if(!passou[adj]){
				passou[adj] = true;
				fila.push(adj);
				nivel[adj] = nivel[v]+1;
			}

		}

	}

}

int main(){

	int n;

	cin >> n;

	int root = -1;

	for(int i=1;i<=n;i++){

		int a;

		cin >> a >> mark[i];

		if(a!=-1){

			grafo[i].push_back(a);
			grafo[a].push_back(i);

		}else{

			root = i;

		}

	}

	bfs(root);

	vector <int> ans;

	for(int i=1;i<=n;i++){

		if(i!=root && mark[i]){

			bool ok = true;

			for(int j=0;j<grafo[i].size();j++){

				int adj = grafo[i][j];

				if(nivel[adj] > nivel[i] && !mark[adj]){
					ok = false;
					break;
				}

			}

			if(ok) ans.push_back(i);

		}

	}

	if(ans.size()==0){
		cout << -1 << endl;
		return 0;
	}

	for(int i=0;i<ans.size();i++){
		cout << ans[i] << " ";
	}

	cout << endl;

	return 0;
}