CustomCC0-1.0#cp-tp3-0142150

Maximal Pairwise Flow Assignment

Summary

•Phase 3 / orientation-flow
•Reasoning-first competitive programming drill

Problem Description

You are given n pairs of nodes (

a_{i}

b_{i}

) and an undirected graph with n nodes and m edges. Assign a direction to each edge so that the maximum number of pairs (

a_{i}

b_{i}

) have a directed path from

a_{i}

b_{i}

. Output this maximal number. How to read this problem in plain language: - This is a Phase 3 reasoning drill focused on orientation-flow. - Typical lenses to test first: graph, orientation, flow. - Constraints reminder: 1 ≤

n \leq 1 e 4;

1 ≤

m \leq 2 e 4

Mini examples for mental simulation: 1) Boundary example: Describe why this case is tricky. Explain expected behavior and why naive logic may fail. 2) Adversarial example: Adversarial case where naive greedy/local decision looks correct but fails globally. Lite-mode writing target: - Write 1~2 observations that shrink the search space. - Name one final algorithm and state target complexity explicitly. - Validate with at least 2 edge cases and one hand simulation.

Constraints

•
1 ≤ $n \leq 1 e 4;$ 1 ≤ $m \leq 2 e 4$

Analysis

Key Insight

Use this hint to refine your reasoning. This step should reduce search space or formalize correctness. State why this insight changes your algorithm choice.

graphorientationflowgreedy