拓扑排序

TODO

待补全

Code

import java.io.*;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static List<Integer>[] adj;
    static int n, m;

    static int[] getInDegree() {
        int[] inDegree = new int[n];
        for (List<Integer> list : adj) {
            for (Integer to : list) {
                ++inDegree[to];
            }
        }
        return inDegree;
    }

    static boolean topologicalSorting() {
        Stack<Integer> S = new Stack<Integer>();
        int[] inDegree = getInDegree();
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] == 0) {
                S.push(i);
            }
        }
        int cnt = 0;
        while (!S.isEmpty()) {
            ++cnt;
            for (Integer to : adj[S.pop()]) {
                if (--inDegree[to] == 0) S.push(to);
            }
        }
        return cnt == n;
    }

    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        adj = new LinkedList[n];
        for (int i = 0; i < n; ++i) adj[i] = new LinkedList<Integer>();
        for (int i = 0; i < m; ++i) adj[nextInt()].add(nextInt());
        topologicalSorting();
    }
}

测试数据

13 15
8 7
7 6
6 9
9 10
9 11
9 12
11 12
6 4
0 6
5 4
0 5
0 1
2 0
2 3
3 5

参考资料

拓扑排序 - OI Wiki