Hi, CodeForces!
I was solving problem 580C — Kefa and Park where I came up with this code: 300260289. However, it fails on test case 8. If I give it the input:
2 1
1 1
1 2
It outputs 0 but when I provide it "2 1" on the last input it would output 1. Why is that happening?
Any help will be deeply appreciated.
EDIT 1: I solved the problem, the error was I was reading the graph (tree) as directed and I hard coded '0' as the root so whenever '0' is not root it bugs!.
The issue arises because your code treats the graph as a directed graph. Specifically, when constructing edges with the following line:
In this case, the input pair $$$(1$$$ $$$2)$$$ is treated differently from $$$(2$$$ $$$1)$$$. However, the problem specifies an undirected graph, meaning both pairs should be treated equivalently. To fix this, you need to construct the graph as undirected by adding edges in both directions:
This ensures that both pairs are handled correctly, maintaining symmetry in the adjacency list.
Additionally, don't forget to adjust the base case in your (DFS) function. For an undirected graph, a leaf node will have exactly one edge (to its parent), not zero.
Aha, thank you for pointing that out.
Auto comment: topic has been updated by MAieshAdnan (previous revision, new revision, compare).