比特城街道定向问题 - 题解

问题本质

将无向图的边定向，使得强连通分量数量最小

关键理论

• 强连通分量(SCC)：任意两点互相可达的最大子图
• 2-边连通分量：没有桥的连通子图
• 核心结论：最小SCC数量 = 2-边连通分量数量

算法思想

1. DFS定向策略

void dfs(int x, int fe) {
    vis[x] = 1;
    for (auto [v, id] : g[x]) {
        int e = abs(id);
        if (e == fe) continue;
        
        // 关键：为未完成的邻居设置边方向
        if (vis[v] != 2) 
            ans[e] = (id < 0) ? '<' : '>';
            
        if (!vis[v]) dfs(v, e);
    }
    vis[x] = 2;
}

定向规则：

• 树边：DFS遍历方向（父→子）
• 回边：后代→祖先（形成环的关键）

2. 为什么这样最优？

• 2-边连通分量 → 通过树边+回边形成环 → 成为SCC
• 桥 → 只能单向 → 连接不同SCC
• 结果：每个2-边连通分量成为一个SCC，桥成为SCC间的连接

代码解析

数据结构设计

vector<pair<int, int>> g[N];  // {邻居, 边ID}
char ans[N];                  // 边方向存储
int vis[N];                   // 0=未访, 1=访问中, 2=已完成

核心流程

int main() {
    // 1. 输入建图（双向存储）
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back({v, i});   // u→v
        g[v].push_back({u, -i});  // v→u  
    }
    
    // 2. DFS确定边方向
    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs(i, 0);
    
    // 3. Tarjan计算SCC数量
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    
    // 4. 输出结果
    cout << scc << "\n";
    for (int i = 1; i <= m; i++) cout << ans[i];
}

Tarjan算法关键点

if ((id > 0) ^ (ans[abs(id)] == '>')) 
    continue;

含义：只考虑在当前定向中有效的边

正确性证明

定理保证

对于任意无向图：

1. 2-边连通分量可以定向为强连通分量
2. 桥必须单向，会分割SCC
3. DFS树定向满足上述条件

直观理解

• 想象DFS遍历过程
• 树边建立"主干道"
• 回边建立"环行路"
• 桥成为"单行线"

复杂度分析

• 时间复杂度：O(n + m)
  • DFS: O(n + m)
  • Tarjan: O(n + m)
• 空间复杂度：O(n + m)

样例验证

输入

7 7
1 2
1 3  
2 3
3 4
4 5
4 5
7 6

处理过程

1. DFS遍历：建立树边和回边
2. 定向结果：><>>><<
3. SCC识别：
   • {1,2,3}（环：1-2-3）
   • {4,5}（平行边形成环）
   • {6}（孤立）
   • {7}（孤立）

输出

4
><>>><<

学习要点

1. 核心技巧

• DFS树的应用：利用遍历树结构确定边方向
• 回边的关键作用：确保环的形成
• 双向存储：高效处理无向图

2. 算法选择理由

• 为什么不用其他方法？
  • 暴力枚举：O(2^m) 不可行
  • 其他定向策略：可能无法保证最优性
  • DFS树定向：理论保证最优 + 高效实现

总结

这道题展示了如何将理论结论转化为高效算法：

1. 理解图的结构性质（2-边连通分量）
2. 设计满足理论要求的构造方法（DFS定向）
3. 验证构造结果（Tarjan算法）