#include <bits/stdc++.h>
using namespace std;

// 返回拓扑序，若检测到环则返回空 vector
vector<int> topoSort(int n, vector<vector<int>>& adj) {
    // 第 1 步：计算入度
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u])
            indegree[v]++;

    // 第 2 步：将所有源点（入度为 0 的顶点）加入队列
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0)
            q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);

        for (int v : adj[u]) {
            indegree[v]--;             // 删除边 u → v
            if (indegree[v] == 0)      // v 的最后一个前置完成
                q.push(v);
        }
    }

    // 若输出不包含所有顶点，说明有环
    if ((int)order.size() != n) return {};  // 检测到环
    return order;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
    }

    vector<int> order = topoSort(n, adj);
    if (order.empty()) {
        cout << "检测到环——不存在拓扑序\n";
    } else {
        for (int v : order) cout << v + 1 << " ";
        cout << "\n";
    }

    return 0;
}

图：0→1, 0→2, 1→3, 2→3, 3→4

初始入度：[0, 1, 1, 2, 1]
队列：[0]

弹出 0 → order=[0]，入度 1→0, 2→0
队列：[1, 2]

弹出 1 → order=[0,1]，入度 3→1
弹出 2 → order=[0,1,2]，入度 3→0
队列：[3]

弹出 3 → order=[0,1,2,3]，入度 4→0
队列：[4]

弹出 4 → order=[0,1,2,3,4]

5 个顶点全部处理完 → 合法的拓扑序！

#include <bits/stdc++.h>
using namespace std;

vector<int> adj_list[100001];
vector<int> topo_order;
int color[100001];  // 0=白色（未访问）, 1=灰色（栈中）, 2=黑色（已完成）
bool has_cycle = false;

void dfs(int u) {
    color[u] = 1;  // 标记为"处理中"
    for (int v : adj_list[u]) {
        if (color[v] == 1) {
            has_cycle = true;  // 后向边 → 有环！
            return;
        }
        if (color[v] == 0)
            dfs(v);
    }
    color[u] = 2;             // 标记为"已完成"
    topo_order.push_back(u);  // 完成子树后再加入结果
}

int main() {
    int n, m;
    cin >> n >> m;
    // ... 读取边 ...

    for (int i = 0; i < n; i++)
        if (color[i] == 0)
            dfs(i);

    reverse(topo_order.begin(), topo_order.end());  // ← 关键：反转完成顺序
    // topo_order 现在是合法的拓扑序
}

// 到达每个顶点的最长路径
vector<int> dp(n, 0);  // dp[v] = 到达 v 的最长路径

// 按拓扑序处理
for (int u : topo_order) {
    for (int v : adj[u]) {
        dp[v] = max(dp[v], dp[u] + edge_weight[u][v]);
        //           ↑ 当前最优    ↑ 通过 u→v 延伸路径
    }
}

int ans = *max_element(dp.begin(), dp.end());

// earliest_start[v] = max(earliest_start[u] + duration[u]) 对所有前驱 u 取最大
vector<int> earliest(n, 0);

for (int u : topo_order) {
    for (int v : adj[u]) {
        earliest[v] = max(earliest[v], earliest[u] + duration[u]);
    }
}

// 项目总完成时间 = max(earliest[v] + duration[v]) 对所有 v
int finish_time = 0;
for (int v = 0; v < n; v++)
    finish_time = max(finish_time, earliest[v] + duration[v]);

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];

int disc[MAXN], low[MAXN], timer_val = 0;
bool on_stack[MAXN];
stack<int> stk;

int scc_id[MAXN];   // 每个顶点属于哪个 SCC？
int scc_count = 0;

void dfs(int u) {
    disc[u] = low[u] = ++timer_val;
    stk.push(u);
    on_stack[u] = true;

    for (int v : adj[u]) {
        if (disc[v] == 0) {          // 树边：v 未访问
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {    // 后向边，属于当前 SCC
            low[u] = min(low[u], disc[v]);
        }
        // 交叉边/前向边（on_stack[v]==false 且 disc[v]!=0）：忽略
    }

    // 若 u 是某个 SCC 的根
    if (low[u] == disc[u]) {
        scc_count++;
        while (true) {
            int v = stk.top(); stk.pop();
            on_stack[v] = false;
            scc_id[v] = scc_count;
            if (v == u) break;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
    }

    for (int i = 0; i < n; i++)
        if (disc[i] == 0)
            dfs(i);

    cout << "SCC 数量：" << scc_count << "\n";
    for (int i = 0; i < n; i++)
        cout << "顶点 " << i << " → SCC " << scc_id[i] << "\n";

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];      // 原图
vector<int> radj[MAXN];     // 转置图（边反向）
bool visited[MAXN];
int scc_id[MAXN];
stack<int> finish_order;

// 第一遍：在原图上 DFS，记录完成顺序
void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v])
            dfs1(v);
    finish_order.push(u);   // 完全处理后压栈
}

// 第二遍：在转置图上 DFS，标记 SCC
void dfs2(int u, int id) {
    visited[u] = true;
    scc_id[u] = id;
    for (int v : radj[u])
        if (!visited[v])
            dfs2(v, id);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
        radj[v].push_back(u);   // 反向边
    }

    // 第一遍：填充 finish_order
    fill(visited, visited + n, false);
    for (int i = 0; i < n; i++)
        if (!visited[i])
            dfs1(i);

    // 第二遍：在转置图上按逆完成顺序处理
    fill(visited, visited + n, false);
    int scc_count = 0;
    while (!finish_order.empty()) {
        int u = finish_order.top(); finish_order.pop();
        if (!visited[u])
            dfs2(u, ++scc_count);
    }

    cout << "SCC 数量：" << scc_count << "\n";
    return 0;
}

// 用 Tarjan 算法找 SCC 后，构建缩点 DAG
// scc_id[v] = 顶点 v 所在的 SCC（1-indexed，拓扑逆序）
// scc_count = SCC 总数

vector<int> scc_adj[MAXN];   // 缩点 DAG 中的边
set<pair<int,int>> seen;      // 避免重复边

for (int u = 0; u < n; u++) {
    for (int v : adj[u]) {
        if (scc_id[u] != scc_id[v]) {
            // 不同 SCC 之间的边
            auto e = make_pair(scc_id[u], scc_id[v]);
            if (!seen.count(e)) {
                seen.insert(e);
                scc_adj[scc_id[u]].push_back(scc_id[v]);
            }
        }
    }
}

// 现在 scc_adj 是 DAG——对其做 DAG DP
// 示例：缩点 DAG 按 SCC 大小加权的最长路径
vector<int> scc_size(scc_count + 1, 0);
for (int i = 0; i < n; i++) scc_size[scc_id[i]]++;

// DAG DP：dp[v] = 以 SCC v 为结尾的路径上的最大顶点数
vector<int> dp(scc_count + 1, 0);
// 按拓扑序处理（Tarjan 给出拓扑逆序，因此从 1 到 scc_count 遍历）
for (int u = 1; u <= scc_count; u++) {
    dp[u] += scc_size[u];
    for (int v : scc_adj[u]) {
        dp[v] = max(dp[v], dp[u]);
    }
}
int ans = *max_element(dp.begin() + 1, dp.end());

// 求解差分约束系统
// 约束：x[b] - x[a] <= w  →  添加边 a→b，权重 w
// 返回最小合法赋值（x[i] = 从虚源到 i 的最短距离）
// 若不可行（含负环）则返回空 vector

vector<long long> solve_difference_constraints(
        int n,                         // n 个变量 x[0..n-1]
        vector<tuple<int,int,int>>& constraints  // {a, b, w}: x[b]-x[a]<=w
) {
    // 添加虚源 s = n，添加边 s→i 权重 0（对所有 i）
    // （使 x[i] >= 0 并提供公共参考点）
    int s = n;
    vector<tuple<int,int,int>> edges = constraints;
    for (int i = 0; i < n; i++)
        edges.push_back({s, i, 0});   // x[i] - x[s] <= 0 → x[i] <= 0

    // 从源点 s 运行 Bellman-Ford
    vector<long long> dist(n + 1, 0);  // 源点距离 = 0

    for (int iter = 0; iter < n; iter++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }

    // 检测负环
    for (auto [u, v, w] : edges) {
        if (dist[u] + w < dist[v])
            return {};  // 含负环 → 无可行解
    }

    return vector<long long>(dist.begin(), dist.begin() + n);
}

#include <bits/stdc++.h>
using namespace std;

struct TwoSat {
    int n;
    vector<vector<int>> adj, radj;
    vector<int> order, comp;
    vector<bool> visited;

    TwoSat(int n) : n(n), adj(2*n), radj(2*n), comp(2*n), visited(2*n) {}

    // 添加子句：(变量 u 取值 val_u) OR (变量 v 取值 val_v)
    // val = true  → 使用节点 2*var
    // val = false → 使用节点 2*var+1
    void add_clause(int u, bool val_u, int v, bool val_v) {
        // ¬(u=val_u) → (v=val_v)
        adj[2*u + !val_u].push_back(2*v + val_v);
        radj[2*v + val_v].push_back(2*u + !val_u);
        // ¬(v=val_v) → (u=val_u)
        adj[2*v + !val_v].push_back(2*u + val_u);
        radj[2*u + val_u].push_back(2*v + !val_v);
    }

    // 强制变量 u 取值 val（添加单元子句：u=val 被强制）
    // 等价于：add_clause(u, val, u, val)
    // 即：要么 u=val 要么 u=val → u 必须为 val
    void force(int u, bool val) {
        // ¬val → val（即若 ¬val 则 val，强制 val 为真）
        adj[2*u + !val].push_back(2*u + val);
        radj[2*u + val].push_back(2*u + !val);
    }

    void dfs1(int v) {
        visited[v] = true;
        for (int u : adj[v])
            if (!visited[u]) dfs1(u);
        order.push_back(v);
    }

    void dfs2(int v, int c) {
        comp[v] = c;
        for (int u : radj[v])
            if (comp[u] == -1) dfs2(u, c);
    }

    // 若可满足返回 true，并将解填入 result[]
    bool solve(vector<bool>& result) {
        // 在蕴含图上运行 Kosaraju SCC
        fill(visited.begin(), visited.end(), false);
        for (int v = 0; v < 2*n; v++)
            if (!visited[v]) dfs1(v);

        fill(comp.begin(), comp.end(), -1);
        int c = 0;
        for (int i = (int)order.size()-1; i >= 0; i--) {
            if (comp[order[i]] == -1)
                dfs2(order[i], c++);
        }

        result.resize(n);
        for (int i = 0; i < n; i++) {
            // 若 xᵢ 和 ¬xᵢ 在同一个 SCC → 矛盾 → 无解
            if (comp[2*i] == comp[2*i+1]) return false;
            // 选择：若 SCC(xᵢ) 的编号大于 SCC(¬xᵢ)，则 xᵢ = true
            // （Kosaraju 给拓扑序较后的 SCC 分配更大的编号）
            result[i] = comp[2*i] > comp[2*i+1];
        }
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;  // n 个变量，m 个子句

    TwoSat sat(n);

    for (int i = 0; i < m; i++) {
        // 读取子句：(x[u] = a) OR (x[v] = b)
        // 其中 u,v 为 0-indexed，a,b 为 0 或 1
        int u, a, v, b;
        cin >> u >> a >> v >> b;
        sat.add_clause(u, a, v, b);
    }

    vector<bool> result;
    if (sat.solve(result)) {
        for (int i = 0; i < n; i++)
            cout << "x[" << i << "] = " << result[i] << "\n";
    } else {
        cout << "不可满足\n";
    }

    return 0;
}

运行 Kahn 算法。若输出包含所有 N 门课程，则无环 → 可以完成。否则有环 → 无法完成。

拓扑排序，然后按拓扑序处理顶点。初始化 dp[S] = 0，dp[其他] = -∞。对每条边 u→v：dp[v] = max(dp[v], dp[u] + w)。

网格是 DAG（移动只向右/向下）。按行主序处理格子（已是拓扑序）。cnt[i][j] = cnt[i-1][j] + cnt[i][j-1]，若 (i,j) 未被封锁。

这是关键路径法（CPM）。运行 Kahn 拓扑排序。对拓扑序中的每个顶点，计算 earliest_start[v] = max(earliest_start[u] + duration[u]) 对所有前驱 u 取最大。答案 = max(earliest_start[v] + duration[v])。

用容斥原理：（经过 ≥1 个标记顶点的路径数）=（所有路径数）-（不经过任何标记顶点的路径数）。对"不经过任何标记顶点"的情形，将标记顶点从图中移除后重新计数。

运行 Tarjan 或 Kosaraju 求 SCC 及其大小。构建缩点 DAG。在缩点 DAG 上做最长路径 DP，每个顶点的"权值"为该 SCC 的大小。答案为 max dp[v]。