有向无环图的拓扑排序

class Solution {
   public:
    bool canFinish(int n, vector<vector<int>>& p) {
        // 存边
        vector<vector<int>> edges(n);
        vector<int> deg(n, 0); // 入度表
        for (auto e : p) {
            edges[e[0]].push_back(e[1]);
            deg[e[1]]++;
        }

        // topo sort
        queue<int> q;
        for (int i = 0; i < n; i++)
            if (deg[i] == 0) q.push(i);

        int cnt = 0;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            cnt++;
            for (auto y : edges[x]) {
                if (--deg[y] == 0) q.push(y);
            }
        }
        return cnt == n; // 判环
    }
};

const int N = 27;
vector<unordered_set<int>> edges;  // edges[x] {y} => x < y
int n; // 节点数目
int a[N];    // 拓扑序结果
int deg[N];  // 入度表

// 0 成功, 1 矛盾, 2 无法确定全序
int solve() {
    // 入度表
    memset(deg, 0, sizeof deg);
    for (int x = 1; x <= n; x++)
        for (auto y : edges[x]) ++deg[y];

    // 同时满足条件矛盾与条件不足, 应该优先输出矛盾, 先看数据有没有矛盾
    int flag = 0;

    // 特判,没有出度的点应该不多于1个
    int c = 0;
    for (int x = 1; x <= n; x++) {
        if (edges[x].empty())
            if (++c > 1) {
                flag = 1; // 延迟返回 2
                break;
            }
    }

    queue<int> q;

    // 加入没有入度的点
    for (int x = 1; x <= n; x++)
        if (deg[x] == 0) q.push(x);

    // 但是, 如果没有入度的点超过 1 个, 说明需要等待继续输入
    if (q.size() > 1) flag = 1;

    // 没有入度 0 的点一定矛盾
    if (q.empty()) return 1;

    int cnt = 0;

    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        a[++cnt] = x;

        int p = 0;  // 计算没有入度的点的个数

        for (auto y : edges[x]) {
            if (--deg[y] == 0) {
                // 没有入度的点超过 1 个, 无法定全序
                if (++p > 1) flag = 1;
                q.push(y);
            }
        }
    }

    if (cnt != n) return 1;  // 矛盾
    if (flag) return 2;      // 条件不足
    return 0;                // 成功
}

const int N = 500 + 1;
int n;
vector<vector<int>> edges; // x => {y1, y2, y3...}
queue<int> q;  // q 是拓扑队列
vector<int> deg; // 入度表
unordered_set<int> rem;  // 待拓扑输出的节点列表

// flag=true 时会操作 rem 集合
// 返回 true 表示无环
bool topo(bool flag) {
    int cnt = rem.size();
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cnt--;
        if (flag) rem.erase(x);
        for (auto y : edges[x])
            if (--deg[y] == 0) q.push(y);
    }
    return cnt == 0;
}

bool solve() {
    // 初始化入度表
    deg.resize(n + 1);
    for (int x = 1; x <= n; x++)
        for (auto y : edges[x]) ++deg[y];

    // 全部加入剩余列表
    for (int x = 1; x <= n; x++) rem.insert(x);

    // 把所有入度 0 的入队
    for (auto x : rem)
        if (deg[x] == 0) q.push(x);

    // 先执行一次拓扑
    if (topo(true)) return true;  // 已经是 DAG

    // 找到所有入度 1 的
    auto deg1 = deg;  // copy
    for (auto x : rem) {
        if (deg[x] != 1) continue;
        deg[x]--; // 删除一个入度, 继续拓扑
        q.push(x); // 入度为 0 的入队
        if (topo(false)) return true;
        deg = deg1; // 恢复入度
    }
    return false;
}

int tot = -1;  // 收集节点标号,从0开始
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> g(m, vector<int>(n, 0));  // g[i][j] -> tot
int N = m * n;
vector<vector<int>> edges(N);
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        g[i][j] = ++tot;
        int v = matrix[i][j];
        if (i > 0) {  // 上边
            int up = matrix[i - 1][j];
            int x = g[i - 1][j];
            if (up < v)
                edges[x].push_back(tot);
            else if (v < up)
                edges[tot].push_back(x);
        }
        if (j > 0) {  // 左边
            int left = matrix[i][j - 1];
            int x = g[i][j - 1];
            if (left < v)
                edges[x].push_back(tot);
            else if (v < left)
                edges[tot].push_back(x);
        }
    }
}

// 入度表
vector<int> deg(N, 0);
for (int x = 0; x < N; x++)
    for (auto y : edges[x]) deg[y]++;
// 拓扑排序
queue<int> q;
vector<int> seq;  // 排序后的结果
for (int x = 0; x < N; x++)
    if (deg[x] == 0) q.push(x);
while (!q.empty()) {
    int x = q.front();
    q.pop();
    seq.push_back(x);
    for (auto y : edges[x])
        if (--deg[y] == 0) q.push(y);
}

// 从后向前 DP 转移
// f(x) 表示 x 开始(包括x) 的最长递增路径的长度, 最开始都为 1
vector<int> f(N, 1);
for (int j = N - 1; j >= 0; j--) {
    auto x = seq[j];
    for (auto y : edges[x]) {
        f[x] = max(f[x], f[y] + 1);
    }
}

// 答案是最终最大的那个 f
return *max_element(f.begin(), f.end());

const int N = 30000 + 5;
int n;
vector<vector<int>> edges;
int ans[N];
int a[N];  // 拓扑序结果

void solve() {
    toposort();

    // V[x] 的第 y 位比特表示 x 是否可以到达 y
    vector<bitset<N>> V(n + 1, 0);

    for (int j = n; j >= 1; j--) { // 倒序
        auto x = a[j];
        V[x].set(x); // 可以到达自身
        for (auto y : edges[x]) V[x] |= V[y]; // 可以到达 y 到达的点
    }

    // 答案
    memset(ans, 0, sizeof ans);
    for (int x = 1; x <= n; x++)
        ans[x] = V[x].count(); // 计算 1 的位数
}

int n = edges.size();
// 拓扑序
vector<int> deg(n, 0);  // 入度表
for (int x = 0; x < n; x++) deg[edges[x]]++;

queue<int> q;
for (int x = 0; x < n; x++)
    if (deg[x] == 0) q.push(x);

vector<int> seq;  // 链上的拓扑序
while (!q.empty()) {
    auto x = q.front();
    q.pop();
    seq.push_back(x);
    auto y = edges[x];
    if (--deg[y] == 0) q.push(y);
}

vector<int> f(n, 0);

// 先更新环上的答案
for (int x = 0; x < n; x++) {
    // 拓扑后环上的点的入度一定非 0
    // 每个环只会遍历 2 次 (f[x] 避免重复访问了)
    if (!deg[x] || f[x]) continue;
    int k = 1;
    // 找环的大小
    for (int y = edges[x]; y != x; y = edges[y]) k++;
    for (int y = x, j = 0; j < k; y = edges[y], j++) f[y] = k;
}

// 反向拓扑序, 更新链上答案
for (int j = seq.size() - 1; j >= 0; j--) {
    auto x = seq[j], y = edges[x];
    f[x] = 1 + f[y];  // x 可以到达 y 和 自身
}

bitset<N> to[N];  // 来源集合

// 倒序求可达, 不包含自身
for (int j = n; j >= 1; j--) {
    int x = seq[j];
    for (auto y : edges[x]) {
        to[x][y] = 1;    // x 可到达 y
        to[x] |= to[y];  // x 可到达 y 的到达
    }
}