题目分析

这是一个在有向图约束下构造有根生成树的问题。需要：

1. 包含所有已建管道
2. 避免使用被禁止的管道
3. 形成一棵有根树（所有边指向根）

关键约束：

• 每个节点只能有一条出边（树的性质）
• 不能形成环
• 某些特定方向的边被禁止

算法思路

核心思想

使用两次DFS + 贪心构造的方法：

1. 第一次DFS：确定根节点和遍历顺序，检查可行性
2. 第二次DFS：按照确定的顺序实际构建树

关键观察

• 已建管道形成部分树结构，需要在此基础上扩展
• 每个节点入度可为任意值，但出度最多为1
• 根节点是没有入度的节点（可以从任意入度为0的节点开始）

代码详解

数据结构定义

int n, m, d;                     // 节点数，已建管道数，禁止边数
int fa[N], deg[N];              // 并查集父节点，入度数组
set<int> bans[N], lft;          // 禁止边集合，候选节点集合
vector<int> vt[N];              // 邻接表（反向边）
vector<pair<int, int>> ans;     // 答案边集

并查集辅助函数

int getf(int x) {
    return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

DFS构造函数

void dfs(int x, int t) {
    // 从候选集合中移除当前节点
    if (lft.find(x) != lft.end())
        lft.erase(x);

    int to = -1;
    
    // 贪心选择可连接的节点
    while (true) {
        auto it = lft.lower_bound(to + 1);  // 从to+1开始查找
        if (it == lft.end()) break;
        
        to = *it;
        
        // 检查是否被禁止
        if (bans[x].find(to) != bans[x].end())
            continue;
        
        // 如果是第二次DFS，添加边
        if (t)
            ans.push_back(make_pair(to, x));
        
        // 递归处理
        dfs(to, t);
    }
    
    // 处理已有子节点（已建管道）
    for (auto &y : vt[x])
        dfs(y, t);
}

主流程

1. 初始化并处理已建管道

scanf("%d%d%d", &n, &m, &d);

// 初始化并查集
for (int i = 0; i < n; i++)
    fa[i] = i;

// 处理已建管道
for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    
    // 检查合法性：x的出度不能超过1，不能形成环
    if (deg[x] > 0 || getf(x) == getf(y)) {
        puts("NO");
        return 0;
    }
    
    // 更新并查集、入度、邻接表
    fa[getf(x)] = getf(y);
    deg[x]++;                     // x的出度增加
    vt[y].push_back(x);           // 反向边：y->x
    ans.push_back(make_pair(x, y));  // 添加到答案
}

2. 处理禁止边

for (int i = 0; i < d; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    bans[y].insert(x);  // 记录从x到y被禁止
}

3. 第一次DFS：确定根和检查可行性

// 收集所有入度为0的节点作为候选根
for (int i = 0; i < n; i++)
    if (!deg[i])
        lft.insert(i);

int rt;  // 根节点
while (!lft.empty()) {
    rt = *lft.begin();  // 选择最小的候选根
    dfs(rt, 0);         // t=0：只遍历，不添加边
}

4. 第二次DFS：实际构建树

// 重新收集候选节点
for (int i = 0; i < n; i++)
    if (!deg[i])
        lft.insert(i);

dfs(rt, 1);  // t=1：实际添加边

// 检查是否所有节点都被处理
if (!lft.empty())
    puts("NO");
else {
    // 输出结果
    for (auto &[x, y] : ans)
        printf("%d %d\n", x, y);
}

算法原理

为什么需要两次DFS？

1. 第一次DFS（t=0）：

   • 确定从候选根开始的遍历顺序
   • 检查是否存在无法连接的节点
   • 确定最终的根节点

2. 第二次DFS（t=1）：

   • 按照第一次确定的顺序实际构建树
   • 添加边到答案中

贪心选择的正确性

算法总是选择编号最小的可用节点连接：

• 这保证了构造的确定性
• 由于解一定存在，贪心策略总能找到解
• 按编号顺序处理避免了随机性

禁止边的处理

bans[y].insert(x) 表示从 x 到 y 的边被禁止。在DFS中：

if (bans[x].find(to) != bans[x].end())
    continue;  // 跳过被禁止的边

注意：存储的是 bans[父节点][子节点] 关系。

复杂度分析

时间复杂度

• 处理已建管道：$O(m α(n))$，其中 $α$ 是反阿克曼函数
• 处理禁止边：$O(d \log n)$
• 两次DFS：$O(n \log n + m)$（每次操作涉及set的查找和删除）
• 总复杂度：$O((n+m+d) \log n)$

空间复杂度

• 并查集：$O(n)$
• 邻接表：$O(n+m)$
• 禁止边集合：$O(d)$
• 候选集合：$O(n)$

样例分析

样例1执行过程

输入：

5 1 8
4 1
3 1
3 4
3 2
0 2
0 4
2 4
1 0
2 0

处理步骤：

1. 已建管道：4->1
2. 入度为0的节点：0, 2, 3（1和4有出度）
3. 第一次DFS确定根为0
4. 第二次DFS构建树：
   • 连接 3->0
   • 连接 1->3
   • 连接 2->3
   • 已有 4->1

输出：

4 1
3 0
1 3
2 3

算法优势

1. 简洁高效：利用set的lower_bound高效查找
2. 正确性保证：通过两次DFS确保构造可行
3. 处理复杂约束：同时处理已建管道和禁止边
4. 灵活性：可以从任意入度为0的节点开始

关键技巧

1. 反向边存储：vt[y].push_back(x) 便于DFS遍历已建结构
2. 集合维护候选：使用set实现高效的查找和删除
3. 贪心编号顺序：确保构造的确定性
4. 两次遍历策略：先检查可行性，再实际构建