×

# Graph problem

 0 problem : NITR02 can someone please explain why i am getting WA my solution: #include #include using namespace std; vector h; vector > 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 13●3 accept rate: 0%

 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 answered 14 Nov, 18:38 61●2 accept rate: 66%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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