7K12 blog

猫でも分かるアルゴリズム解説

DAGの性質まとめ

【木のDAG】
木に単一の方向性を持たせるとDAGになる
割り振り直した頂点IDは降順あるいは昇順になる
このようなDAGは木でもあるので元の頂点IDはユニークでもある

頂点の割り振り直し方法
・DAGの最長経路=木の根からの深さ=末端からMAXのBFS、で頂点IDを割り振り直すと最小化
・根からBFSまたはDFSで頂点IDを割り振り直すと全頂点ユニークIDになる、このとき頂点IDは最大化される

【一般的なDAG】
割り振り直した頂点IDは降順あるいは昇順、元の頂点IDはユニーク

頂点の割り振り直し方法
・DAGの最長経路=木の根からの深さ=末端からMAXのBFS、で頂点IDを割り振り直すと最小化

例題 https://atcoder.jp/contests/abc139/tasks/abc139_e