闲的蛋疼，用 shell 写了个拓扑排序。。。

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

› Bash Reference Manual

这是一个创建于 1673 天前的主题，其中的信息可能已经有所发展或是发生改变。

#!/usr/bin/env bash

if graph="$(mktemp -d)" || { echo failed; exit 2; } then
    trap 'rm -rf "${graph}"' exit
fi

while read start end; do
    mkdir -p "${graph}/${end}/${start}" "${graph}/${start}"
done

while [[ $(ls -1 "${graph}" | wc -l) -gt 0 ]]; do
    for u in ${graph}/*; do
        [[ $(ls -1 "${u}" | wc -l) -eq 0 ]] && { echo "$(basename ${u})"; break; }
    done | {
        read pop || { echo cylic; exit 1; }

        echo "${pop}"
        rmdir "${graph}/${pop}"

        for v in ${graph}/*; do
            [[ -d "${v}/${pop}" ]] && rmdir "${v}/${pop}"
        done
    }
done

大家看看写得对吗？

附赠输入输出：

CSCI-E-50a  CSCI-E-50b
CSCI-E-50b  CSCI-E-160
CSCI-E-160  CSCI-E-162
CSCI-E-50b  CSCI-E-119
CSCI-E-119  CSCI-E-215
CSCI-E-119  CSCI-E-124
CSCI-E-50b  MATH-E-104
MATH-E-10   CSCI-E-119
MATH-E-10   MATH-E-104
MATH-E-104  CSCI-E-124

CSCI-E-50a
CSCI-E-50b
CSCI-E-160
CSCI-E-162
MATH-E-10
CSCI-E-119
CSCI-E-215
MATH-E-104
CSCI-E-124

玩得开心～

2 条回复 • 2020-04-25 12:08:14 +08:00

BiteTheDust

2020-04-25 12:05:35 +08:00

这是向用 cmake 写红黑树看齐吗

aheadlead

2020-04-25 12:08:14 +08:00

@BiteTheDust #1 拓扑排序简单多了吧。。。