AtCoder Beginner Contest 478

E lt and le

前置知识：Kosaraju

题目大意

给定长度为 $N$ 的正整数序列 $A$，序列中每个元素需满足 $1\le A_i\le N$。现有 $Q$ 条约束条件，每条约束由三元组 $(t_i,u_i,v_i)$ 给定：

• 若 $t_i=0$：要求 $A_{u_i}\le A_{v_i}$；
• 若 $t_i=1$：要求 $A_{u_i}<A_{v_i}$。

请判定是否存在满足全部 $Q$ 条约束的序列 $A$。若存在，输出 Yes 并构造任意一组满足条件的解；若不存在，输出 No。

数据范围：

• $1\le N\le 2\times {10}^5$
• $1\le Q\le 2\times {10}^5$
• $t_i\in \{0,1\}$
• $1\le u_i,v_i\le N$
• 所有输入均为整数。

---

思路

本题可抽象为一类差分约束系统与有向图最长路问题。

1. 约束转化与图论建模：

• 对于 $t_i=0$ 的非严格不等式 $A_{u_i}\le A_{v_i}$，等价于 $A_{v_i}\ge A_{u_i}+0$，可从 $u_i$ 向 $v_i$ 连一条有向边，权值为 $0$。
• 对于 $t_i=1$ 的严格不等式 $A_{u_i}<A_{v_i}$，在整数域下等价于 $A_{v_i}\ge A_{u_i}+1$，可从 $u_i$ 向 $v_i$ 连一条有向边，权值为 $1$。

2. 强连通分量 (SCC) 缩点：

• 若图中存在一个有向环，环上所有顶点满足 $A_{v_1}\le A_{v_2}\le \cdots \le A_{v_k}\le A_{v_1}$，则环上全部节点的取值必须严格相等。
• 若环内存在至少一条权值为 $1$ 的严格小于边，则会推导出 $A_{v_1}<A_{v_1}$ 的矛盾，此时判定无解，直接输出 No。
• 因此，可以通过 Kosaraju 或 Tarjan 算法求出原图的所有强连通分量（SCC）。同一分量内部所有顶点的取值必须相同，且同一分量内部不允许存在权值为 $1$ 的自环或环边。

3. 利用 Kosaraju 编号特性的 DAG 最长路 DP：

• 缩点后原图转化为有向无环图（DAG）。
• 拓扑序性质：Kosaraju 算法在反图上第二次遍历时，按照原图后序遍历数组的逆序分配连通块。若存在分量间的前向边 $C_1\to C_2$，在原图 DFS 中 $C_2$ 必然先于 $C_1$ 结束遍历，因此逆序处理时 $C_1$ 必然先于 $C_2$ 被访问。换言之，分配得到的 SCC 编号 $1\sim \text{cnt}$ 天然构成了缩点后 DAG 的一个有效拓扑排序。
• 设 $f[u]$ 表示分量 $u$ 的最小合法取值，初始时置为基准下界 $f[u]=1$。
• 按编号 $u=1\to \text{cnt}$ 顺序遍历各个分量，遍历所有跨分量出边 $(u\to v,w)$，执行最长路松弛：

$$f[v]=max(f[v],f[u]+w)$$

• 由于序列元素有上限限制 $A_i\le N$，遍历过程中若出现任一分量满足 $f[u]>N$，说明最长依赖链长度已超过值域上限，判定无解；否则，令 $A_i=f[\text{scc}[i]]$ 即可得到一组满足条件的构造。

---

复杂度分析

时间复杂度：

• 构建原图与反图需要 $\mathcal{O}(N+Q)$ 时间。
• Kosaraju 算法进行两次深度优先遍历求解强连通分量的时间复杂度为 $\mathcal{O}(N+Q)$。
• 遍历所有约束边以检测环内合法性并建立分量出边图，耗时 $\mathcal{O}(Q)$。
• 在 DAG 上沿拓扑序进行动态规划，各点与各边被访问常数次，耗时 $\mathcal{O}(N+Q)$。
• 综合总时间复杂度为 $\mathcal{O}(N+Q)$，可在限制时间内高效通过。

空间复杂度：

• 原图、反图与缩点后 DAG 边的邻接表占用空间为 $\mathcal{O}(N+Q)$。
• 节点访问标记 vis、SCC 映射数组 scc、DFS 后序记录 org 及 DP 数组 f 等均占用 $\mathcal{O}(N)$ 空间。
• 综合总空间复杂度为 $\mathcal{O}(N+Q)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct edge{
    int t,u,v;
};
void fc() {
    int n,q;std::cin>>n>>q;

    // g: 原图邻接表, rg: 反图邻接表
    std::vector<std::vector<int>>g(n+1),rg(n+1);
    std::vector<int>scc(n+1);
    int cnt=0;
    std::vector<int>org;
    std::vector<bool>vis(n+1);
    std::vector<edge>e(q+1);

    for(int i=0;i<q;i++){
        std::cin>>e[i].t>>e[i].u>>e[i].v;
        g[e[i].u].push_back(e[i].v);
        rg[e[i].v].push_back(e[i].u);
    }

    // Kosaraju 算法第一阶段：记录后序遍历序列
    auto dfs1=[&](auto&&self,int u)->void{
        vis[u]=true;
        for(auto& v:g[u]){
            if(!vis[v])self(self,v);
        }
        org.push_back(u);
    };

    // Kosaraju 算法第二阶段：在反图上回溯标记连通块
    auto dfs2=[&](auto&&self,int u,int c)->void{
        scc[u]=c;
        for(auto& v:rg[u]){
            if(!scc[v])self(self,v,c);
        }
    };
    for(int i=1;i<=n;i++)if(!vis[i])dfs1(dfs1,i);
    // 逆序访问产生的 cnt 标号天然构成 DAG 拓扑序
    for(int i=n-1;i>=0;i--)if(!scc[org[i]])dfs2(dfs2,org[i],++cnt);

    // 缩点并建立新图边表
    std::vector<std::vector<std::pair<int,int>>>deg(cnt+1);
    for(int i=0;i<q;i++){
        if(scc[e[i].u]==scc[e[i].v]){
            // 同一强连通分量内出现严格小于边，则产生矛盾
            if(e[i].t){std::cout<<"No";return;}
        }else{
            deg[scc[e[i].u]].push_back({scc[e[i].v],e[i].t});
        }
    }

    // 拓扑序最长路 DP
    std::vector<int>f(cnt+1,1);
    for(int u=1;u<=cnt;u++){
        if(f[u]>n){
            std::cout<<"No";return;
        }
        for(auto& [v,t]:deg[u]){
            f[v]=std::max(f[v],f[u]+t);
        }
    }

    std::cout<<"Yes\n";
    for(int i=1;i<=n;i++)std::cout<<f[scc[i]]<<" ";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}