In the following code,
<code>#include <iostream>
#include <vector>
using namespace std;
vector <int> otm;
vector <int> past;
vector <int> strength;
bool leaves(int n){
for (int i = 0; i < n; i++){
if (otm[i] == 1 && past[i] == 0 && strength[i] < strength[0]){
return true;
}
}
return false;
}
int main()
{
int n;
cin >> n;
otm.resize(n, 1);
for (int i = 0; i < n; i++){
int a;
cin >> a;
strength.push_back(a);
}
int prep[n];
past.resize(n, 0);
for (int i = 0; i < n - 1; i ++){
int a;
int b;
cin >> a >> b;
prep[b - 1] = a - 1;
past[a - 1]++;
}
while (leaves(n)){
for (int i = 0; i < n; i++){
if (otm[i] == 1 && past[i] == 0 && strength[i] < strength[0]){ //this is 48 line
otm[i] = 0;
past[prep[i]]--;
}
}
}
int sum = 0;
for (int i = 0; i < n; i++){
if (otm[i] == 1){
sum++;
}
}
cout << sum - 1;
}
</code>
<code>#include <iostream>
#include <vector>
using namespace std;
vector <int> otm;
vector <int> past;
vector <int> strength;
bool leaves(int n){
for (int i = 0; i < n; i++){
if (otm[i] == 1 && past[i] == 0 && strength[i] < strength[0]){
return true;
}
}
return false;
}
int main()
{
int n;
cin >> n;
otm.resize(n, 1);
for (int i = 0; i < n; i++){
int a;
cin >> a;
strength.push_back(a);
}
int prep[n];
past.resize(n, 0);
for (int i = 0; i < n - 1; i ++){
int a;
int b;
cin >> a >> b;
prep[b - 1] = a - 1;
past[a - 1]++;
}
while (leaves(n)){
for (int i = 0; i < n; i++){
if (otm[i] == 1 && past[i] == 0 && strength[i] < strength[0]){ //this is 48 line
otm[i] = 0;
past[prep[i]]--;
}
}
}
int sum = 0;
for (int i = 0; i < n; i++){
if (otm[i] == 1){
sum++;
}
}
cout << sum - 1;
}
</code>
#include <iostream>
#include <vector>
using namespace std;
vector <int> otm;
vector <int> past;
vector <int> strength;
bool leaves(int n){
for (int i = 0; i < n; i++){
if (otm[i] == 1 && past[i] == 0 && strength[i] < strength[0]){
return true;
}
}
return false;
}
int main()
{
int n;
cin >> n;
otm.resize(n, 1);
for (int i = 0; i < n; i++){
int a;
cin >> a;
strength.push_back(a);
}
int prep[n];
past.resize(n, 0);
for (int i = 0; i < n - 1; i ++){
int a;
int b;
cin >> a >> b;
prep[b - 1] = a - 1;
past[a - 1]++;
}
while (leaves(n)){
for (int i = 0; i < n; i++){
if (otm[i] == 1 && past[i] == 0 && strength[i] < strength[0]){ //this is 48 line
otm[i] = 0;
past[prep[i]]--;
}
}
}
int sum = 0;
for (int i = 0; i < n; i++){
if (otm[i] == 1){
sum++;
}
}
cout << sum - 1;
}
changing line 48 to:
if (otm[i] == 1 && past[i] == 0 && strength[i] > strength[0]){
like its supposed to be, it goes into an infinite loop. Any ideas as to why it leads to an infinite loop?
New contributor
Yuri Korostelev is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.