E. Dead-End Detector
The council of your home town has decided to improve road sign placement, especially for dead ends. They have given you a road map, and you must determine where to put up signs to mark the dead ends. They want you to use as few signs as possible. The road m...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
The council of your home town has decided to improve road sign placement, especially for dead ends. They have given you a road map, and you must determine where to put up signs to mark the dead ends. They want you to use as few signs as possible. The road map is a collection of locations connected by two-way streets. The following rule describes how to obtain a complete placement of dead-end signs. Consider a street S connecting a location x with another location. The x-entrance of S gets a dead-end sign if, after entering S from x, it is not A dead-end sign. possible to come back to x without making a U-turn. A U-turn is a 180- Source: Wikimedia Commons degree turn immediately reversing the direction. To save costs, you have decided not to install redundant dead-end signs, as specified by the following rule. Consider a street S with a dead-end sign at its x-entrance and another street T with a dead-end sign at its y-entrance. If, after entering S from x, it is possible to go to y and enter T without making a U-turn, the dead-end sign at the y-entrance of T is redundant. See Figure E.1 for examples.
5 8
1 3 6
5 1
2 74 6 2 3 4(a) Sample Input 1 (b) Sample Input 2Figure E.1: Illustration of sample inputs, indicating where non-redundant dead-end signs
are placed.Input
The first line of input contains two integers n and m, where n (1 ≤ n ≤ 5 · 105 ) is the number of locations and m (0 ≤ m ≤ 5 · 105 ) is the number of streets. Each of the following m lines contains two integers v and w (1 ≤ v < w ≤ n) indicating that there is a two-way street connecting locations v and w. All location pairs in the input are distinct.
Output
On the first line, output k, the number of dead-end signs installed. On each of the next k lines, output two integers v and w marking that a dead-end sign should be installed at the v-entrance of a street connecting locations v and w. The lines describing dead-end signs must be sorted in ascending order of v-locations, breaking ties in ascending order of w-locations.
Sample Tests
6 5
1 2
1 3
2 3
4 5
5 62
4 5
6 58 8
1 2
1 3
2 3
3 4
1 5
1 6
6 7
6 83
1 5
1 6
3 4Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
Connected components are independent, so we can reason about one component at a time.
If a component is a tree, then every edge direction pointing away from a leaf is a dead end. Among these, only the signs placed at leaf entrances are non-redundant, because every other dead-end entrance can be reached from one of those leaf signs.
If a component contains a cycle, then the non-dead-end part is exactly its $2$-core: repeatedly remove leaves until no degree-$1$ vertices remain. The removed vertices form trees hanging off the core.
In such a component, the only non-redundant signs are the street entrances from the core into those hanging trees. Once you move from the core into such a tree, you can never come back to the core without a U-turn. Any deeper dead-end sign inside that tree is redundant, because it is reachable after first entering the core-to-tree street.
Algorithm
Build the undirected graph and compute connected components.
Repeatedly peel leaves with a queue:
start with every vertex of degree at most $1$,
remove it,
decrease the degrees of its remaining neighbors,
if one of them becomes degree $1$, push it too.
After this process, the unremoved vertices are exactly the $2$-core.
For every edge with exactly one endpoint in the core, output the sign directed from the core endpoint to the removed endpoint.
For every connected component whose core is empty, the component is a tree (or an isolated vertex). In that case, output the sign from each original leaf to its only neighbor.
Sort all output pairs lexicographically. enumerate
Correctness Proof
We prove that the algorithm outputs exactly the non-redundant dead-end signs.
Lemma 1.
In a tree component, the non-redundant dead-end signs are exactly the signs from leaves to their unique neighbors.
Proof.
If we enter a tree edge from a leaf into the tree, then at the next vertex we are not allowed to reverse immediately, and every further move only goes deeper into some subtree. Therefore we can never return to that leaf, so the sign is a dead end.
Now consider any dead-end sign $u \to v$ where $u$ is not a leaf. Since the component is a tree, some leaf $w$ exists in the subtree reached from $u \to v$. After entering the street from $w$ toward the tree, we can follow the unique path to $u$ and then enter $u \to v$ without making a U-turn. Hence the sign at $u \to v$ is redundant. So only leaf-to-neighbor signs remain. □
Lemma 2.
In a component with non-empty $2$-core, every removed vertex lies in a tree attached to the core, and every edge from the core to such a tree is a dead-end entrance.
Proof.
Repeated leaf removal deletes exactly the vertices that are not part of any cycle, leaving the $2$-core. The removed vertices therefore form disjoint trees attached to core vertices.
Take an edge from a core vertex $u$ to a removed vertex $v$. After traversing $u \to v$, we are inside one of those attached trees. To get back to $u$, we would need to reverse along the unique path to the core, but that would eventually require an immediate reversal on the first edge of that path. Thus returning to $u$ without a U-turn is impossible, so $u \to v$ is a dead-end entrance. □
Lemma 3.
In a component with non-empty $2$-core, every dead-end sign strictly inside one of the removed trees is redundant.
Proof.
Let $x \to y$ be a dead-end sign inside an attached tree. Consider the unique edge from the core into that tree, say $u \to v$. After entering $u \to v$, we can continue along the unique path inside the tree until we reach $x$, and then enter $x \to y$ without making a U-turn. Therefore $x \to y$ is redundant. □
Theorem.
The algorithm outputs exactly the non-redundant dead-end signs.
Proof.
By Lemma 1, tree components contribute exactly the leaf-to-neighbor signs. By Lemma 2, every edge from the core to a removed tree is a dead-end entrance. By Lemma 3, these are the only non-redundant ones in components with non-empty core. Since components are independent, taking the union over all components gives exactly the required set of signs. □
Complexity Analysis
The leaf-peeling process touches every vertex and edge $O(1)$ times, and the final scan over edges is linear as well. Therefore the running time is $O(n + m)$ and the memory usage is $O(n + m)$.
Implementation Notes
The algorithm needs the original degrees to detect leaves in a tree component after peeling. The code therefore uses the adjacency list size for that special case and a separate mutable degree array for the queue process.
Isolated vertices contribute no signs.
Sorting the final list of directed edge pairs directly gives the output order required by the statement.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
struct Edge {
int to;
int id;
};
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int> > edges(m);
vector<vector<Edge> > graph(n + 1);
vector<int> degree(n + 1, 0);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
edges[i] = make_pair(u, v);
graph[u].push_back({v, i});
graph[v].push_back({u, i});
++degree[u];
++degree[v];
}
vector<int> comp(n + 1, -1);
vector<int> comp_edge_count;
vector<vector<int> > comp_vertices;
int comp_cnt = 0;
for (int start = 1; start <= n; ++start) {
if (comp[start] != -1) {
continue;
}
queue<int> q;
q.push(start);
comp[start] = comp_cnt;
comp_vertices.push_back({});
long long degree_sum = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
comp_vertices.back().push_back(v);
degree_sum += graph[v].size();
for (const Edge& e : graph[v]) {
if (comp[e.to] == -1) {
comp[e.to] = comp_cnt;
q.push(e.to);
}
}
}
comp_edge_count.push_back((int)(degree_sum / 2));
++comp_cnt;
}
queue<int> q;
vector<char> removed(n + 1, false);
for (int v = 1; v <= n; ++v) {
if (degree[v] <= 1) {
q.push(v);
}
}
while (!q.empty()) {
int v = q.front();
q.pop();
if (removed[v] || degree[v] > 1) {
continue;
}
removed[v] = true;
for (const Edge& e : graph[v]) {
if (removed[e.to]) {
continue;
}
--degree[e.to];
if (degree[e.to] == 1) {
q.push(e.to);
}
}
}
vector<char> comp_has_core(comp_cnt, false);
for (int v = 1; v <= n; ++v) {
if (!removed[v]) {
comp_has_core[comp[v]] = true;
}
}
vector<pair<int, int> > answer;
for (int id = 0; id < m; ++id) {
int u = edges[id].first;
int v = edges[id].second;
if (removed[u] != removed[v]) {
if (!removed[u]) {
answer.push_back(make_pair(u, v));
} else {
answer.push_back(make_pair(v, u));
}
}
}
for (int cid = 0; cid < comp_cnt; ++cid) {
if (comp_has_core[cid]) {
continue;
}
for (int v : comp_vertices[cid]) {
if ((int)graph[v].size() == 1) {
answer.push_back(make_pair(v, graph[v][0].to));
}
}
}
sort(answer.begin(), answer.end());
cout << answer.size() << '\n';
for (const pair<int, int>& sign : answer) {
cout << sign.first << ' ' << sign.second << '\n';
}
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2019/E-dead-end-detector/solution.texC++ implementationcompetitive_programming/icpc/2019/E-dead-end-detector/solution.cppStatement textcompetitive_programming/icpc/2019/E-dead-end-detector/statement.txtStatement PDFcompetitive_programming/icpc/2019/E-dead-end-detector/statement.pdfMetadatacompetitive_programming/icpc/2019/E-dead-end-detector/meta.jsonYear packetcompetitive_programming/icpc/2019/contest_problems.pdf