T01094: Sorting It All Out

topological sort, http://cs101.openjudge.cn/practice/01094/

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

输入

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

输出

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y. Sorted sequence cannot be determined. Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

样例输入

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

样例输出

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

来源

East Central North America 2001

python

#23n2310307206胡景博
from collections import deque
def topo_sort(graph):
    in_degree = {u:0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    q = deque([u for u in in_degree if in_degree[u] == 0])
    topo_order = [];flag = True
    while q:
        if len(q) > 1:
            flag = False#topo_sort不唯一确定
        u = q.popleft()
        topo_order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    if len(topo_order) != len(graph): return 0
    return topo_order if flag else None
while True:
    n,m = map(int,input().split())
    if n == 0: break
    graph = {chr(x+65):[] for x in range(n)}
    edges = [tuple(input().split('<')) for _ in range(m)]
    for i in range(m):
        a,b = edges[i]
        graph[a].append(b)
        t = topo_sort(graph)
        if t:
            s = ''.join(t)
            print("Sorted sequence determined after {} relations: {}.".format(i+1,s))
            break
        elif t == 0:
            print("Inconsistency found after {} relations.".format(i+1))
            break
    else:
        print("Sorted sequence cannot be determined.")

python

# 23n2300011335
def topo_sort(v):
    global vis,pos,T,topo
    if vis[v] == -1:
        return -1
    if pos[v] != -1:
        return pos[v]
    vis[v] = -1
    p = n
    for i in range(len(T[v])):
        p = min(p,topo_sort(T[v][i]))
        if p == -1:
            return -1
    topo[p-1] = v
    pos[v],vis[v] = p-1,0
    return p-1
while True:
    n,m = map(int,input().split())
    if n == m == 0:
        break
    T = [[] for _ in range(n)]
    E = []
    for _ in range(m):
        s = input()
        E.append([ord(s[0])-ord('A'),ord(s[2])-ord('A')])
    topo = [0 for _ in range(n)]
    for i in range(m):
        p = E[i]
        T[p[0]].append(p[1])
        ans = n
        vis = [0 for _ in range(n)]
        pos = [-1 for _ in range(n)]
        for j in range(n):
            ans = min(ans,topo_sort(j))
        if ans == -1:
            print(f'Inconsistency found after {i+1} relations.')
            break
        elif ans == 0:
            print(f'Sorted sequence determined after {i+1} relations: {"".join([chr(topo[k]+ord("A")) for k in range(n)])}.')
            break
    if ans > 0:
        print("Sorted sequence cannot be determined.")

Q. 有没有能够随时跟进图的变化的拓扑排序算法。而不是每次图变化都要重新排一遍。

下面是一个可直接 AC，并且真正“增量”维护拓扑序的 Python 实现。它在每次插入一条新边时，只做一次受限的 BFS 和一次局部数组搬移，最坏 O(n+m)，但是常见场景下远快于重排全图。

python

from collections import deque, defaultdict

def kahn_check(adj, nodes):
    """
    改进的 Kahn 算法，用来判断当前图是否：
      - 有环，返回 0
      - 唯一拓扑序，返回该序列 list
      - 多解，返回 None
    """
    in_deg = {u: 0 for u in nodes}
    for u in adj:
        for v in adj[u]:
            in_deg[v] += 1

    q = deque(u for u in nodes if in_deg[u] == 0)
    topo = []
    unique = True
    while q:
        if len(q) > 1:
            unique = False
        u = q.popleft()
        topo.append(u)
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)

    if len(topo) < len(nodes):
        return 0      # 有环
    return topo if unique else None

def forward_reachable(adj, start, pos, hi):
    """
    从 start 沿出边做 BFS，只收集那些 pos[w] ≤ hi 的节点。
    """
    seen = {start}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in seen and pos[v] <= hi:
                seen.add(v)
                q.append(v)
    return seen

def solve():
    import sys
    for line in sys.stdin:
        line = line.strip().split()
        if not line:
            continue
        n, m = map(int, line)
        if n == 0 and m == 0:
            break

        # 节点 A, B, ..., chr(ord('A')+n-1)
        nodes = [chr(ord('A') + i) for i in range(n)]
        adj   = defaultdict(list)

        # 初始序列就是 A, B, C, ...
        order = nodes[:]
        pos   = {u:i for i,u in enumerate(order)}

        def insert_edge(u, v):
            """
            插入 u->v：
            1) 如果 pos[u] < pos[v]，无需调整
            2) 否则
               F = 所有能从 v 出发（沿原图）到达且 pos[...] ≤ pos[u] 的节点
               若 u∈F 则成环，返回 False
               否则把 F 从 order 中摘出，插到 u 之后，更新 pos，返回 True
            """
            adj[u].append(v)
            if pos[u] < pos[v]:
                return True

            F = forward_reachable(adj, v, pos, pos[u])
            if u in F:
                return False

            # 从 order 中删掉 F
            new_order = [w for w in order if w not in F]
            # 找 u 在删完 F 后的新位置
            idx = new_order.index(u)
            # 保持 F 在旧 order 中的相对次序
            F_list = [w for w in order if w in F]

            # 重建 order：u 之后插入 F_list
            order.clear()
            order.extend(new_order[:idx+1])
            order.extend(F_list)
            order.extend(new_order[idx+1:])

            # 更新 pos
            for i,w in enumerate(order):
                pos[w] = i
            return True

        # 读入每条关系，在线处理
        rels = [sys.stdin.readline().strip() for _ in range(m)]
        done = False
        for i, rel in enumerate(rels, start=1):
            u, v = rel.split('<')
            ok = insert_edge(u, v)
            if not ok:
                print(f"Inconsistency found after {i} relations.")
                done = True
                break
            chk = kahn_check(adj, nodes)
            if isinstance(chk, list):
                print(f"Sorted sequence determined after {i} relations: {''.join(chk)}.")
                done = True
                break

        if not done:
            print("Sorted sequence cannot be determined.")

if __name__ == "__main__":
    solve()

说明

数据结构
- order：当前维护的一个合法拓扑序列。
- pos[u]：节点 u 在 order 中的下标。
- adj：邻接表，增量插入。
增量更新逻辑
1. 向 adj 添加 u→v。
2. 若 pos[u] < pos[v]，说明原序列已满足 u<v，无需改动。
3. 否则，从 v 出发做一次受限 BFS，只收集那些 pos[w] ≤ pos[u] 的可达节点 F。
  - 若 u∈F，则新边与原路径 v→…→u 构成环，直接报错。
  - 否则，取 F 在原 order 中的相对次序，整体摘出并插到 u 之后，再更新所有 pos。
唯一性检测 每插完一条边后，调用一次改进的 Kahn 算法（kahn_check），它在处理队列时监测“可选入度为 0 的节点”是否超过 1，以此判定序列是否唯一。

这样，就能做到真正的“在线”增量维护——只有受影响部分被重排，避免了全图重走一遍拓扑排序。

T01094: Sorting It All Out ​

T01094: Sorting It All Out