🏆Meta Hacker Cup 2012 Round 2-B: Road Removal

Difficulty: Medium-Hard Topic: Graph Theory & Spanning Forests

Problem Summary

You have N cities connected by M undirected roads (edges). The first K cities are marked as “important.” Your goal: remove the minimum number of roads such that no cycle contains any important city.

In other words, important cities must form a forest (acyclic structure). Roads between important cities can exist, but they cannot create any cycles. Cycles not involving any important city are allowed to remain.

This is equivalent to finding a spanning forest of the subgraph induced by important cities, then determining how many edges to remove.

Sample Walkthrough

Input:

5 5 2
1 2
2 3
3 1
4 5
1 4

Interpretation: 5 cities, 5 roads, 2 important cities (cities 1 and 2)

Graph:

Analysis:

• Roads: 1–2, 2–3, 3–1, 4–5, 1–4
• Important cities: 1, 2
• Cycle 1–2–3–1 contains important cities (1 and 2)
• To break this cycle, remove at least 1 edge connecting important cities or their neighbors in the cycle
• Minimum removal: 1 road

Answer: 1

Solution Approach

Naive Approach (Understanding Phase)

Find all cycles, check which contain important cities, and greedily remove edges:

function naiveRoadRemoval(n, k, edges) {
  // Build adjacency list
  const graph = Array.from({ length: n + 1 }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }
  let removed = 0;
  // For each edge, try removing it and check if cycles still exist
  for (const [u, v] of edges) {
    // Remove edge (u, v)
    // Check if important cities still form a cycle
    // If removing it helps, keep it removed
  }
  return removed;
}

Problem: This is exponential in complexity. Finding all cycles and checking each removal is too slow.

Optimized Approach (Union-Find)

The key insight: A forest is a graph with no cycles. The maximum number of edges in a forest of K nodes is K-1.

For important cities only:

• If they form C connected components, the maximum edges in a forest = K — C
• Current edges in the induced subgraph = E_important
• Edges to remove = E_important — (K — C)

WHY? Use union-find to add edges one by one. When adding an edge would create a cycle (both endpoints already in the same component), we must remove it.

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // already connected → would create cycle
    // Union by rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true; // successfully joined components
  }
}
function optimalRoadRemoval(n, k, edges) {
  // Union-find for important cities (indexed 0 to k-1)
  const uf = new UnionFind(k);
  let edgesToRemove = 0;
  // Process each edge
  for (const [u, v] of edges) {
    // Check if both endpoints are important
    if (u <= k && v <= k) {
      // Try to add this edge to the forest
      const added = uf.union(u - 1, v - 1); // convert to 0-indexed
      if (!added) {
        // Edge would create a cycle → must remove
        edgesToRemove++;
      }
    }
  }
  return edgesToRemove;
}

Why this works: We only care about cycles within important cities. By building a spanning forest using union-find, we accept the first K-1 edges and reject any edge that would close a cycle. Edges not connecting two important cities are irrelevant.

Complete Solution

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false;
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true;
  }
}
function solve(input) {
  const lines = input.trim().split('\n');
  const testCases = parseInt(lines[0]);
  let lineIdx = 1;
  const results = [];
  for (let tc = 0; tc < testCases; tc++) {
    const [n, m, k] = lines[lineIdx++].split(' ').map(Number);
    const edges = [];
    for (let i = 0; i < m; i++) {
      const [u, v] = lines[lineIdx++].split(' ').map(Number);
      edges.push([u, v]);
    }
    // Union-find for the k important cities (1-indexed, convert to 0-indexed)
    const uf = new UnionFind(k);
    let removed = 0;
    // Process each edge
    for (const [u, v] of edges) {
      // Only consider edges between important cities
      if (u <= k && v <= k) {
        // Attempt to add this edge to the forest
        // If both endpoints already in same component, it creates a cycle
        const canAdd = uf.union(u - 1, v - 1);
        if (!canAdd) {
          // Would create a cycle → remove this edge
          removed++;
        }
      }
    }
    results.push(`Case #${tc + 1}: ${removed}`);
  }
  return results.join('\n');
}
// Example usage
const input = `1
5 5 2
1 2
2 3
3 1
4 5
1 4`;
console.log(solve(input));

Output:

Case #1: 1

Complexity Analysis

AspectComplexityReasoningTimeO(M · α(K))M edges, union-find with path compressionSpaceO(K)Union-find data structure for K important citiesα(K)Nearly ConstantInverse Ackermann function, effectively O(1) for practical inputs

Test Snippet

const testCases = [
  {
    input: `1\n5 5 2\n1 2\n2 3\n3 1\n4 5\n1 4`,
    expected: `Case #1: 1`
  },
  {
    input: `1\n4 4 3\n1 2\n2 3\n3 1\n1 4`,
    expected: `Case #1: 1` // triangle among important cities
  },
  {
    input: `1\n3 2 2\n1 2\n2 3`,
    expected: `Case #1: 0` // no cycles involving important cities
  },
  {
    input: `1\n5 5 5\n1 2\n2 3\n3 4\n4 5\n5 1`,
    expected: `Case #1: 1` // all cities important, pentagon cycle
  }
];

testCases.forEach(({ input, expected }) => {
  const output = solve(input);
  console.log(output === expected ? '✓ PASS' : `✗ FAIL\nGot: ${output}\nExpected: ${expected}`);
});

Key Takeaways

1. Spanning Forest Concept: A forest with K nodes and C connected components has exactly K-C edges. This is fundamental to solving minimum edge removal problems.
2. Union-Find Efficiency: The union-find data structure with path compression and union by rank runs in near-constant time per operation, making it ideal for cycle detection.
3. Cycle Detection via Union-Find: When both endpoints of an edge are already in the same component, adding that edge creates a cycle. This is the core principle.
4. Problem Restriction: Only edges between important cities matter. Edges involving non-important cities can be ignored entirely.
5. Greedy Forest Building: Always accept the first K-C edges that don’t create cycles. This greedy approach is optimal for spanning forests.

If you liked the article please clap and follow :) Thx and stay tuned 🚀 **Linkedin**