题目描述L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
差分约束系统，就是给定一些 $ x_i - x_j >= d $ 的不等式，求出其中的一组解。我们可以转化为最短路来解决该类问题。
概念我们先来明确一些概念。子图图G=(V，E)，G’=(V’，E’)中，若V’ ∈ V，E’ ∈ E，并且E’中的边所关联的顶点都在V’中，则称图G’是图G的子图强连通性对有向图G=(V,E)而言，若对于G中任意两个顶点Vi和Vj（Vi≠Vj ），都有一条从Vi到Vj的（有向路径），同时还有一条从Vj到Vi的(有向)路径，则称有向图G是强连通的强连通分量（SCC）有向图强连通的 极大 子图