Hawk-and-Chicken

题目解析

dag上能到达点u的点的数量

时间复杂度 $n^2$ 能过,

这是一份基于你的模板（linkList + TarjanScc）完成的 HDU 3639 Hawk-and-Chicken 的完整代码。

核心思路回顾

Tarjan缩点：处理循环依赖，将强连通分量缩成一个点，点权为该分量包含的原节点数。
构建反向DAG：原题求“谁被最多人指向”，反向后变为“从谁出发能指向最多人”。

原图：
反向DAG：

剪枝 DFS：在反向DAG中，只有 入度为0 的点（原图的汇点）才可能是最终赢家。从这些点出发 DFS 统计能覆盖的总点权。

代码实现

注意：HDU 3639 的输入是 0 ~ N-1，但你的 Tarjan 模板循环是从 1 ~ N。为了适配模板，我在读入时将节点编号 +1，输出时再 -1。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * Problem: HDU 3639 Hawk-and-Chicken
 * Method: Tarjan SCC + Reverse Graph + DFS
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;

const int maxn = 5005;   // 题目 N <= 5000
const int maxm = 30005;  // 题目 M <= 30000

// ---------------- 你的模板开始 ----------------

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxm * 2]; // 稍微开大一点防止越界
    int h[maxn],edge_cnt=0;
    linkList(){ reset(); }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }

    // 迭代器部分为了简洁省略，本题直接用原生循环更高效
} e, edag; // e: 原图, edag: 反向DAG

struct TarjanScc {
    int n, timer;
    std::stack<int> st;
    bool in_stack[maxn];
    int dfn[maxn], low[maxn], scc_id[maxn];
    int scc_cnt; 

    void set(int _n) {
        n = _n;
        timer = scc_cnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(in_stack, 0, sizeof(in_stack));
        while(!st.empty()) st.pop();
    }

    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        in_stack[u] = true;

        for (int i = e.h[u]; ~i ; i = e.e[i].next) {
            int v = e.e[i].v;
            if (!dfn[v]) { 
                dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if (in_stack[v]) { 
                low[u] = std::min(low[u], dfn[v]);
            }
        }

        if (low[u] == dfn[u]) {
            scc_cnt++;
            while (1) {
                int v = st.top(); st.pop();
                in_stack[v] = 0;
                scc_id[v] = scc_cnt; 
                if (v == u) break; 
            }
        }
    }

    void solve() {
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) dfs(i);
        }
    }
} tarjan;

// ---------------- 你的模板结束 ----------------

// 全局变量
int scc_sz[maxn];    // 每个 SCC 的大小（点权）
int dag_indeg[maxn]; // 反向 DAG 的入度
int vis[maxn];       // DFS 访问标记
int visit_token = 0; // 时间戳，避免 memset vis
int current_sum = 0; // 当前 DFS 统计的总数

// 简单的 DFS 统计: 统计从 u 出发能到达的所有点的点权和
void dfs_calc(int u) {
    vis[u] = visit_token;
    current_sum += scc_sz[u];
    
    // 遍历反向图 edag
    for(int i = edag.h[u]; ~i; i = edag.e[i].next) {
        int v = edag.e[i].v;
        if(vis[v] != visit_token) {
            dfs_calc(v);
        }
    }
}

void solve(int n, int m, int case_id) {
    // 1. Tarjan 缩点
    tarjan.solve();

    // 2. 初始化统计数组
    for(int i = 0; i <= tarjan.scc_cnt; i++) {
        scc_sz[i] = 0;
        dag_indeg[i] = 0;
    }
    edag.reset(); // 清空反向图

    // 3. 计算每个 SCC 的大小 (原图点权)
    for(int i = 1; i <= n; i++) {
        scc_sz[tarjan.scc_id[i]]++;
    }

    // 4. 构建反向 DAG
    // 遍历原图的所有边 u -> v
    for(int u = 1; u <= n; u++) {
        for(int i = e.h[u]; ~i; i = e.e[i].next) {
            int v = e.e[i].v;
            int su = tarjan.scc_id[u];
            int sv = tarjan.scc_id[v];
            
            // 如果不在同一个 SCC，建立反向边: SCC[v] -> SCC[u]
            if(su != sv) {
                edag.add(sv, su); // 反向！
                dag_indeg[su]++;  // 统计入度
            }
        }
    }

    // 5. 寻找最大支持数
    int max_val = -1;
    // 存储每个 SCC 能获得的总支持数，-1表示未计算或非起点
    vector<int> final_score(tarjan.scc_cnt + 1, -1);
    
    visit_token = 0;
    memset(vis, 0, sizeof(vis));

    for(int i = 1; i <= tarjan.scc_cnt; i++) {
        // 剪枝：只从反向图入度为 0 的点（原图汇点）开始搜
        if(dag_indeg[i] == 0) {
            visit_token++;
            current_sum = 0;
            dfs_calc(i);
            
            // 题目要求不包含自己，所以结果是 current_sum - 1
            // 但为了比较方便，我们先存总数
            final_score[i] = current_sum;
            max_val = max(max_val, current_sum);
        }
    }

    // 6. 输出结果
    printf("Case %d: %d\n", case_id, max_val - 1);
    
    vector<int> ans_nodes;
    for(int i = 1; i <= n; i++) {
        // 如果节点 i 所属的 SCC 获得的支持数等于最大值
        if(final_score[tarjan.scc_id[i]] == max_val) {
            ans_nodes.push_back(i - 1); // 变回 0-based 输出
        }
    }
    
    // 排序并输出
    sort(ans_nodes.begin(), ans_nodes.end());
    for(int i = 0; i < ans_nodes.size(); i++) {
        if(i > 0) printf(" ");
        printf("%d", ans_nodes[i]);
    }
    printf("\n");
}

int main() {
    int t;
    if(scanf("%d", &t) == 1) {
        for(int i = 1; i <= t; i++) {
            int n, m;
            scanf("%d %d", &n, &m);
            
            // 初始化
            e.reset();
            tarjan.set(n);
            
            for(int j = 0; j < m; j++) {
                int u, v;
                scanf("%d %d", &u, &v);
                // 题目输入 0~n-1，转为 1~n 适配模板
                e.add(u + 1, v + 1);
            }
            
            solve(n, m, i);
        }
    }
    return 0;
}

时间复杂度

我们来详细分析一下这份“Tarjan缩点 + 反向图 + 剪枝DFS”代码的时间复杂度。

1. 复杂度结论

假设：

$N$ 为点数（ $N \le 5000$ ）
$M$ 为边数（ $M \le 30000$ ）
$T$ 为数据组数（ $T \le 50$ ）
$K$ 为缩点后，反向图中入度为0的连通分量个数（即原图中出度为0的汇点SCC数量）。

总时间复杂度为：

O(T \times (N + M + K \times (N + M)))

简化后的最坏时间复杂度（当 $K \approx N$ 时）：

O(T \times N \times (N + M))

空间复杂度为：

O(N + M)

2. 分步详细分析

第一步：Tarjan 缩点

操作：遍历整个图的每个点和每条边一次。
复杂度： $O(N + M)$ 。

第二步：构建反向图 (Reverse DAG)

操作：遍历原图的所有边，判断是否跨越 SCC，若是则加入新图。
复杂度： $O(N + M)$ 。
- 注意：虽然可能有重边，但这一步是线性的。

第三步：DFS 统计 (核心瓶颈)

这是决定生死的步骤。

单次 DFS：在反向 DAG 上进行一次 DFS，最坏情况下会遍历整个反向图。反向图的点数 $\le N$ ，边数 $\le M$ 。复杂度 $O(N + M)$ 。
执行次数：我们做了剪枝，只对反向图中入度为0的点（Candidate Roots）发起 DFS。假设这样的点有 $K$ 个。
Token 优化的作用：visit_token 使得我们将每次 DFS 前的清空操作从 $O(N)$ 降为 $O(1)$ ，这非常关键，但不会改变 DFS 本身的遍历复杂度。
该步骤复杂度： $O(K \times (N + M))$ 。

3. 为什么这个复杂度能过？(风险评估)

让我们算一下最坏情况的数据量：

50 \text{ (组)} \times 5000 \text{ (点)} \times 35000 \text{ (点+边)} \approx 8.75 \times 10^9 \text{ 次操作}

通常计算机 1秒只能处理约 $10^8$ 次操作。理论上，这个复杂度是会超时的 (TLE)。

但是它能过的原因如下：

缩点 (SCC) 的威力：
- 如果图中有大环，缩点后 $N$ 会急剧减小。例如一个强连通图缩点后 $N=1, M=0$ ，复杂度瞬间变成 $O(1)$ 。
- 复杂度公式里的 $N$ 和 $M$ 其实是缩点后的点数 $N'$ 和边数 $M'$ 。通常 $N' \ll N$ 。
剪枝 ( $K$ ) 的威力：
- 虽然最坏情况 $K \approx N$ （例如每一层节点都指向下一层，像金字塔形状），但在随机数据或典型数据中，汇点 (Sink Nodes) 的数量通常不多。
- 如果图是一个长链（ $1 \to 2 \to \dots \to N$ ），反向后入度为0的点只有1个 ( $K=1$ )。此时复杂度仅为 $O(N+M)$ 。
- 如果图是一个从中心向外发射的星形，反向后入度为0的点虽然有 $N-1$ 个，但每次 DFS 深度只有 1，总计算量依然很小。
Token 优化：
- 如果不加 visit_token，每次 DFS 前 memset 清空数组，复杂度会变成 $O(K \times (N + (N+M)))$ ，常数变大，极大概率 TLE。Token 优化去掉了这个 $O(N)$ 的初始化开销。

4. 另一种更稳的算法 (Bitset)

如果这道题的数据构造得非常“恶心”（DAG 图，没有环，且有很多菱形结构导致 $K$ 很大且每次 DFS 覆盖面很广），上述算法会 TLE。

在竞赛中，处理这类 $N \le 5000$ 的DAG可达性统计问题，更稳定的是使用 std::bitset 优化拓扑排序：

原理： $Reach[u] = \{u\} \cup Reach[v_1] \cup Reach[v_2] \dots$
做法：在 DAG 上跑逆拓扑排序，用 bitset 做或运算（OR）。
复杂度： $O(\frac{N(N+M)}{64})$ 。
计算： $\frac{8.75 \times 10^9}{64} \approx 1.3 \times 10^8$ ，这在 1-2秒内是绝对安全的。

5. 总结

目前使用的 DFS + Pruning 方案：

平均/随机数据：飞快。
特定构造数据 (Dense DAG)：会 TLE。
针对 HDU 3639：这道题的数据比较弱，且 $N=5000$ 在旧题库中往往允许 $O(N^2)$ 级别的算法通过（特别是带有大常数剪枝的）。

代码是正确且适合该题的标准解法之一。

目录