[Codeforces 1391E] Pairs of Pairs

Problem Description

Problem Link

Given a undirected connected graph, with n vertices and m edges, find either

1. A path that at least (n+1) / 2 long.
2. A pairing with at least (n+1)/2, where the induced subgraph of any pair of pairs is with at most 2 edges.

Solution

Solution from the tutorial

DFS Tree

The DFS tree of an undirected graph, are with two kind of edges, the Tree Edge and Backward Edge. If there is a path between u and v, u and v are ancestor-descendants.

(The DFS tree of a directed graph, are with four kind of edges, the Tree Edge, Forward Edge, Backward Edge and Cross Edge.)

Constructive Method

So, if there is a vertex is with depth >= (n+1)/2, we can get a path. Otherwise, we can pair the vertices with the same depth. The number of vertices we can use is at least n - max depth > n - (n+1)/2 >= (n+1)/2. For two pairs<a, b>, <c, d>, if a is connected with c and d, since <a, c, d> are ancestor-descendants, c and d cannot be on the same level. Therefore, the pairing is valid.

Code.

Posts

• [Codeforces 1391E] Pairs of Pairs

• [Codeforces 1393D] Rarity and New Dress

• Convex Hull Trick

• [Codeforces 1389G] Directing Edges

• [Codeforces 1389F] Bicolored Segments

• [Codeforces 1381C] Mastermind

• [Codeforces 1375G] Tree Modification

• [Codeforces 1375F] Integer Game

• [Codeforces 1375E] Inversion SwapSort

subscribe via RSS