Hints : Alternating Path
Answer to Hint 1: For all length-1 paths $v \to u$ to be alternating, every first step must go along the edge direction. So every edge incident to $v$ must be oriented out of $v$ (i.e., $v$ has only outgoing edges in the directed graph).
Assume $v$ is “good”. Pick any neighbor $u$ of $v$ and consider paths $v \to u \to x$. The second step must traverse an edge against its direction. What does that force about edges incident to $u$?
Answer to Hint 2: Since the second move must go opposite the directed edge, every edge leaving $u$ in the undirected graph must be directed into $u$ (so that traversing $u \to x$ goes against direction $x \to u$). In other words, such a neighbor $u$ must have only incoming edges.
You should see two “roles” emerging for vertices:
- one role where all incident edges must be oriented outward
- the opposite role where all incident edges must be oriented inward
Try labeling vertices by role based on their distance parity from $v$.
Answer to Hint 3: The roles alternate by distance from $v$: vertices at even distance must be “all outgoing”, and vertices at odd distance must be “all incoming” (or the reverse, depending on the chosen start role).
If you commit to these two roles, then every undirected edge must connect vertices of opposite roles (otherwise one edge can’t be oriented to satisfy both endpoints). What familiar graph property is this describing?
Answer to Hint 4: This is exactly a 2-coloring constraint: endpoints of every edge must have different colors (a bipartition).
Translate the previous hint into a contradiction on cycles: walk around a cycle and flip role each step. What happens if the cycle length is odd?
Answer to Hint 5: On an odd cycle, flipping roles each step forces you to return to the start with the opposite role—impossible. So any component containing an odd cycle can’t satisfy the required role constraints.
So, for a connected component:
- if it fails that property, it contributes 0 beautiful vertices no matter how you direct edges
- if it satisfies the property, vertices split into two groups (call them color 0 and color 1)
Now guess a direction rule based purely on color.
Answer to Hint 6: If the component can be 2-colored (no conflicts), then you can orient edges consistently by color: direct every edge from one color class to the other.
Try orienting every edge consistently from one color to the other. Check what kinds of starting vertices automatically have the “alternating for all paths” behavior under that orientation.
Answer to Hint 7: Under a consistent orientation (say color 0 $,\to,$ color 1), every vertex in the “source” color has all edges going out, and every vertex in the other color has all edges coming in. The “all outgoing” side are exactly the candidates that satisfy the forced first-step condition everywhere in the component.
In a “good” component, you essentially have two symmetric choices (flip all directions). One choice makes all vertices of color 0 beautiful; the other makes all vertices of color 1 beautiful. Which is better?
Answer to Hint 8: Choose the orientation that makes the larger color class the “beautiful” side.
Therefore, a good component’s contribution can be computed from just the sizes of its two color classes. You don’t need to actually build the directed graph—just count during DFS/BFS.
Answer to Hint 9: For a bipartite component with color sizes $c_0, c_1$, the best you can do is $\max(c_0, c_1)$. For a non-bipartite component, it’s $0$.
Implementation pattern:
- run DFS/BFS from every unvisited node, assigning alternating colors
- if you ever revisit a node with the wrong color, mark the component as “bad”
- otherwise add $\max(color0,color1)$ to the answer