奶牛野餐地点选择问题题解

一、题目分析

题目要求找出所有奶牛都能到达的牧场数量，关键条件：

• K头奶牛分别位于不同牧场，牧场间有单向路径；
• 需计算所有奶牛都能到达的牧场数目。

二、算法思路

1. 图模型：将牧场视为节点，路径视为有向边，构建有向图；
2. 可达性分析：对每头奶牛的起始牧场进行DFS，记录其能到达的所有牧场；
3. 统计公共可达牧场：若某牧场被所有奶牛的DFS标记为可达，则计入结果。

三、代码实现

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

int k, n, m;
vector<int> v[1001];  // 邻接表存储有向图
int at[101];         // 存储每头奶牛的起始牧场
bool b[1001];        // DFS访问标记数组
int sum[1001];       // 记录每个牧场被多少头奶牛到达

// DFS函数：标记从x出发可达的所有牧场
void dfs(int x) {
    b[x] = true;
    int next;
    for (int i = 0, len = v[x].size(); i < len; ++i) {
        next = v[x][i];
        if (b[next]) continue;  // 已访问则跳过
        dfs(next);
    }
}

int main() {
    int i, j;
    cin >> k >> n >> m;
    
    // 读取每头奶牛的起始牧场
    for (i = 1; i <= k; i++)
        scanf("%d", at + i);
    
    // 读取路径并构建邻接表
    while (m--) {
        scanf("%d%d", &i, &j);
        v[i].push_back(j);
    }
    
    memset(sum, 0, sizeof(sum));  // 初始化统计数组
    memset(b, false, sizeof(b));  // 初始化访问标记
    
    // 对每头奶牛进行DFS，统计可达牧场
    for (i = 1; i <= k; ++i) {
        dfs(at[i]);
        for (j = 1; j <= n; ++j)
            sum[j] += b[j], b[j] = false;  // 记录可达情况并重置标记
    }
    
    // 统计所有奶牛都能到达的牧场数量
    int ans = 0;
    for (i = 1; i <= n; ++i) {
        if (sum[i] == k)
            ans++;
    }
    
    printf("%d\n", ans);
    return 0;
}

四、代码解释

1. 输入处理：

   • 读取奶牛数量K、牧场数量N、路径数量M；
   • 读取每头奶牛的起始牧场，以及所有单向路径。

2. DFS遍历：

   • 对每头奶牛的起始牧场执行DFS，标记其能到达的所有牧场；
   • 每次DFS后，将可达牧场的计数sum[j]加1，并重置标记数组b。

3. 结果统计：

   • 若某牧场的计数sum[i]等于奶牛数量K，说明所有奶牛都能到达，计入答案。

五、示例解析

输入样例：

2 4 4  
2  
3  
1 2  
1 4  
2 3  
3 4  

1. 奶牛1（起始牧场2）的可达牧场：2→3→4；
2. 奶牛2（起始牧场3）的可达牧场：3→4；
3. 统计sum数组：
   • 牧场3：sum[3]=2（两头奶牛都可达）；
   • 牧场4：sum[4]=2（两头奶牛都可达）；
4. 输出：2。

六、复杂度分析

• 时间复杂度：O(K*(N+M))，其中K为奶牛数量，N为牧场数，M为路径数；
  • 每头奶牛执行DFS的时间为O(N+M)，共K次。
• 空间复杂度：O(N+M)，用于存储邻接表和标记数组。

七、关键技巧

1. 邻接表存储：高效存储有向图，适合稀疏图；
2. DFS可达性标记：通过标记数组记录可达牧场，简单直观；
3. 计数数组统计：用sum[i]记录牧场i被多少头奶牛到达，快速判断公共可达性。