You are not logged in. Please login at www.codechef.com to post your questions!

×

Graph problem

problem : NITR02 can someone please explain why i am getting WA
my solution:

#include <iostream>
#include <vector>
using namespace std;
vector<int> h;
vector<vector<int> > v;
void dfs(int node, int heigt = 0) {

    if(v[node].size() == 0) {  // storing all the heights
        h.push_back(heigt);
        return;
    }
    int siz = v[node].size();

    for(int i = 0; i < siz; ++i) {
        int x = v[node][i];

        dfs(x, heigt + 1);
    }
}

int main() {
    int n;
    cin >> n;
    v.resize(n+1);
    for(int i = 1; i < n; ++i) {
        int x; cin >> x;
        v[x].push_back(i+1);
    }
    int mx = 0;
    dfs(1);
    for(int i = 0; i < h.size(); ++i) {  // getting the maximum
        mx = max(mx, h[i]);
    }
    int count = 0;
    for(int i = 0; i < h.size(); ++i) {  // for comman heights we have to extra work
        if(h[i] == mx) {
            count++;  // counting no of maximum values
        }
    }
    if(n == 1){
        cout << 0;
        return 0;
    }
    cout << mx + count - 1;


}

asked 14 Nov, 18:01

vipin_bhardwaj's gravatar image

3★vipin_bhardwaj
133
accept rate: 0%


Just like root needs to do extra work for common heights, internal nodes also need to do that extra work. For eg - If subtree of node al height 1 also has leaves at equal height from the top, then your solution will give wrong answer. Consider this test case - 1 1 2 2 3 3 (n=7) . Correct answer is 4 but your method will give 2+1 = 3

link

answered 14 Nov, 18:38

himanshu_0896's gravatar image

5★himanshu_0896
612
accept rate: 66%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×952
×469

question asked: 14 Nov, 18:01

question was seen: 48 times

last updated: 14 Nov, 18:38