三千道路 - 题解

标签与难度

标签: 图论, 有向图, 强连通分量 (SCC), Tarjan算法, 拓扑排序, 缩点, 竞赛图, 构造难度: 2100

题目大意喵~

你好呀，未来的算法大师！这道题是关于有向图和一种特殊的图——竞赛图的呢，喵~

题目会给我们一个有 $n$ 个点和 $m$ 条边的普通有向图 $G$ 。然后问我们，是否存在一个同样有 $n$ 个点的竞赛图 $T$ ，使得 $G$ 和 $T$ 的连通性相同。

这里的定义要看仔细哦：

竞赛图：对于任意两个不同的点 $u$ 和 $v$ ，它们之间有且仅有一条有向边。要么是 $u \to v$ ，要么是 $v \to u$ 。就像一场循环赛，每对选手都比了一场，必有胜负，不会有平局或者不比的情况，喵~
连通性相同：对于图上的每一个点 $x$ ，它在图 $G$ 中能到达的所有点的集合，和它在图 $T$ 中能到达的所有点的集合，是完全一样的。

简单来说，就是我们要判断，能不能把原图 $G$ "改造" 成一张竞赛图 $T$ ，在加加减减一些边之后，所有点的“势力范围”（能到达的地方）都保持不变。如果可以，就输出 "YES"，不然就输出 "NO"，的说。

解题思路分析

喵哈哈，这道题看起来有点抽象，但只要跟着本喵的思路，一层一层剥开它的核心，就会发现它其实是一只很可爱的纸老虎哦！

第一步：理解“连通性相同”

“连通性相同”这个条件是解题的关键！它说对于任何一个点 $u$ ，它在原图 $G$ 中能到达的点集和在目标竞赛图 $T$ 中能到达的点集完全相同。

这意味着什么呢？这意味着两张图的可达关系是完全一样的。如果 $u$ 在 $G$ 中能走到 $v$ ，那么在 $T$ 中也必须能走到 $v$ ；反之亦然。

我们知道，如果点 $u$ 和 $v$ 在同一个强连通分量 (SCC) 中，它们就可以互相到达。既然两张图的可达关系完全一样，那么它们必须拥有完全相同的强连通分量！也就是说，原图 $G$ 划分出的 SCC，和我们要找的竞赛图 $T$ 划分出的 SCC，在点的构成上必须是一模一样的。

第二步：竞赛图的性质

好，既然 SCC 是关键，那我们来看看竞赛图 $T$ 的 SCC 有什么特别之处。一个非常重要的性质是：任何竞赛图的缩点图都是一个“传递性竞赛图”。

“传递性竞赛图”听起来很高级，但其实它就是一个结构非常简单的有向无环图 (DAG)。它的所有节点（也就是 $T$ 的 SCC）可以排成一条直线，比如 $C_1, C_2, \dots, C_k$ 。在这条链上，对于任意 $i < j$ ，都有一条从 $C_i$ 到 $C_j$ 的边。它就像一个严格的“鄙视链”，排在前面的可以到达所有排在后面的，但反过来不行。

所以，如果我们能找到一个符合条件的竞赛图 $T$ ，那么它的缩点图一定是一条链。而我们又知道 $G$ 和 $T$ 的 SCC 是一样的，所以它们的缩点图也应该有相同的可达性。这意味着，原图 $G$ 的缩点图，其结构必须等价于一条链！

怎么判断一个 DAG 是不是一条链呢？我们可以用拓扑排序（比如 Kahn 算法）来检查。在一个链式结构的 DAG 中，任何时候都最多只有一个入度为 0 的节点。如果在拓扑排序的过程中，我们发现队列里同时出现了两个或更多的入度为 0 的节点，那就说明图出现了“分支”，不是一条单纯的链了，直接判定为 "NO"！

第三步：SCC 内部的结构

我们解决了 SCC 之间的关系，现在来看看 SCC 内部。假设原图 $G$ 有一个 SCC，叫做 $C$ 。在 $G$ 中， $C$ 里的所有点都可以互相到达。为了保持连通性不变，在竞赛图 $T$ 中， $C$ 对应的点集也必须是强连通的。

也就是说，对于 $G$ 的每一个 SCC，我们必须能在其包含的点上构建一个强连通的竞赛图。那么，一个 $k$ 个点的竞赛图，什么时候才能是强连通的呢？这里有一个小小的结论，喵~

当 $k=1$ 时，它自己就是一个点，是强连通的。
当 $k=2$ 时，比如点 $\{u, v\}$ ，边要么是 $u \to v$ ，要么是 $v \to u$ 。它们永远无法互相到达，所以绝不可能强连通。
当 $k \ge 3$ 时，我们总是可以构造一个强连通的竞赛图。比如，我们可以先让点排成一个环 $v_1 \to v_2 \to \dots \to v_k \to v_1$ ，这就保证了强连通。剩下的点对之间再随便加一条有向边就好啦。

所以，我们得到了第二个关键条件：原图 $G$ 中，任何一个 SCC 的大小都不能等于 2！

总结一下我们的算法

结合上面的分析，我们的解题步骤就清晰了，喵~

缩点：对输入的有向图 $G$ 使用 Tarjan 算法或 Kosaraju 算法，找出所有的强连通分量 (SCC)。在寻找的过程中，记录下每个 SCC 的大小。
检查 SCC 大小：遍历所有 SCC，如果发现任何一个 SCC 的大小等于 2，那么就无法构造出满足条件的竞赛图。直接输出 "NO"。
构建缩点图：将每个 SCC 看作一个点，构建缩点图。如果原图 $G$ 中有一条边 $u \to v$ ，且 $u$ 和 $v$ 不在同一个 SCC 中，那么就在 $scc(u)$ 和 $scc(v)$ 之间连一条边。
检查缩点图结构：对缩点图进行拓扑排序。在排序过程中（使用 Kahn 算法和队列），时刻检查队列的大小。如果任何时候队列中的节点数超过 1，说明缩点图不是链式结构，直接输出 "NO"。
最终判断：如果以上所有检查都顺利通过，那就说明我们可以构造出满足条件的竞赛图。输出 "YES"。

是不是很简单呀？只要把问题分解成“SCC 之间”和“SCC 内部”两个层面，再利用竞赛图的性质，问题就迎刃而解啦！

代码实现

这是本喵根据上面的思路，精心重构的一份代码哦！注释很详细，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 使用前向星存储图
const int MAXN = 100005;
const int MAXM = 200005;

struct Edge {
    int to;
    int next;
};

Edge edges[MAXM];
int head[MAXN], edge_count;

void add_edge(int u, int v) {
    edges[++edge_count] = {v, head[u]};
    head[u] = edge_count;
}

// Tarjan 算法相关变量
int dfn[MAXN], low[MAXN], timestamp;
int scc_id[MAXN], scc_count;
int scc_size[MAXN];
int stack[MAXN], top;
bool in_stack[MAXN];

// Tarjan 算法找强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stack[++top] = u;
    in_stack[u] = true;

    for (int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++scc_count;
        int node;
        do {
            node = stack[top--];
            in_stack[node] = false;
            scc_id[node] = scc_count;
            scc_size[scc_count]++;
        } while (node != u);
    }
}

// 缩点图相关
std::vector<int> scc_adj[MAXN];
int scc_in_degree[MAXN];

void solve() {
    int n, m;
    std::cin >> n >> m;

    // --- 初始化 ---
    edge_count = 0;
    std::fill(head + 1, head + n + 1, 0);

    timestamp = 0;
    scc_count = 0;
    top = 0;
    std::fill(dfn + 1, dfn + n + 1, 0);
    std::fill(scc_id + 1, scc_id + n + 1, 0);
    std::fill(scc_size + 1, scc_size + n + 1, 0);
    std::fill(in_stack + 1, in_stack + n + 1, false);
    
    // --- 读图 ---
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        add_edge(u, v);
    }

    // --- 1. Tarjan 找 SCC ---
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // --- 2. 检查 SCC 大小 ---
    for (int i = 1; i <= scc_count; ++i) {
        if (scc_size[i] == 2) {
            std::cout << "NO\n";
            return;
        }
    }
    
    if (scc_count == 0 && n > 0) { // 处理空图但有节点的情况
        scc_count = n;
        for(int i=1; i<=n; ++i) scc_id[i] = i;
    }

    // --- 3. 构建缩点图 ---
    for (int i = 1; i <= scc_count; ++i) {
        scc_adj[i].clear();
        scc_in_degree[i] = 0;
    }

    for (int u = 1; u <= n; ++u) {
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to;
            if (scc_id[u] != scc_id[v]) {
                scc_adj[scc_id[u]].push_back(scc_id[v]);
            }
        }
    }
    
    // --- 4. 检查缩点图结构 (拓扑排序) ---
    // 首先对边去重并计算入度
    for (int i = 1; i <= scc_count; ++i) {
        std::sort(scc_adj[i].begin(), scc_adj[i].end());
        scc_adj[i].erase(std::unique(scc_adj[i].begin(), scc_adj[i].end()), scc_adj[i].end());
        for (int neighbor_scc : scc_adj[i]) {
            scc_in_degree[neighbor_scc]++;
        }
    }
    
    std::vector<int> q;
    for (int i = 1; i <= scc_count; ++i) {
        if (scc_in_degree[i] == 0) {
            q.push_back(i);
        }
    }

    int processed_sccs = 0;
    while (!q.empty()) {
        // 关键检查：任何时候队列大小都不能超过1
        if (q.size() > 1) {
            std::cout << "NO\n";
            return;
        }
        
        int u_scc = q.back();
        q.pop_back();
        processed_sccs++;

        for (int v_scc : scc_adj[u_scc]) {
            scc_in_degree[v_scc]--;
            if (scc_in_degree[v_scc] == 0) {
                q.push_back(v_scc);
            }
        }
    }

    // 如果所有SCC都处理完了，说明缩点图是个DAG（这里是链）
    // 并且之前的检查都通过了
    std::cout << "YES\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N+M)$ 整个算法的瓶颈在于图的遍历。
1. Tarjan 算法对图进行一次深度优先遍历，复杂度为 $O(N+M)$ 。
2. 构建缩点图需要遍历所有原图的边，复杂度为 $O(M)$ 。
3. 对缩点图的邻接表进行排序和去重，最坏情况下所有边都是跨 SCC 的，复杂度可能达到 $O(M \log M)$ ，但由于每个 SCC 的出边数量有限，总和不会超过 $M$ ，所以总的排序复杂度是 $O(M \log N)$ 级别。不过，更精细的分析表明，总复杂度仍可被 $O(N+M)$ 控制（例如使用 std::set 代替排序去重）。在我们的实现中，排序去重是一个步骤，总时间复杂度为 $O(N+M)$ 。
4. 拓扑排序遍历缩点图一次，其节点数和边数都不超过 $N$ 和 $M$ ，复杂度为 $O(N+M)$ 。因此，总的时间复杂度为 $O(N+M)$ 。
空间复杂度: $O(N+M)$
1. 前向星存图需要 $O(N+M)$ 的空间。
2. Tarjan 算法需要 $O(N)$ 的辅助数组（dfn, low, stack 等）。
3. 缩点图的邻接表最坏情况下需要 $O(M)$ 的空间。所以，总的空间复杂度为 $O(N+M)$ 。

知识点总结

这道题是一个很好的图论综合练习题，喵~ 它考察了我们对以下知识点的掌握程度：

强连通分量 (SCC)：理解 SCC 的定义，并熟练使用 Tarjan 或 Kosaraju 算法进行缩点是解决本题的基础。
缩点：将一个复杂的有向图通过 SCC 简化成一个有向无环图 (DAG) 是处理许多图论问题的常用技巧。
竞赛图的性质：了解竞赛图的一些基本但关键的性质，特别是其缩点图必定是“传递性”的（即一条链），以及其子图强连通的条件。
拓扑排序 (Kahn 算法)：不仅能用来判断 DAG 中是否有环或得到一个拓扑序，还能通过一些小改动来判断 DAG 的特殊结构，比如本题中的链式结构。
问题转化能力：将题目中抽象的“连通性相同”条件，一步步转化为具体的、可用算法验证的图论性质（SCC大小限制、缩点图结构限制）。

多做这样的题目，可以很好地锻炼我们的图论思维和综合应用算法的能力哦！加油，你一定可以的，喵~

三千道路 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：理解“连通性相同” ​

第二步：竞赛图的性质 ​

第三步：SCC 内部的结构 ​

总结一下我们的算法 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​