洛谷：P2853：Cow Picnic S

题目

P2853：Cow Picnic S

分析

这道题看着像并查集，但并不是。并查集的特性告诉我们，最终能得到有几个独立的集合，但这些独立的集合是“隔离”的，和题意中要求的“所有奶牛都能到”的要求相悖。

我是倒过来想的：

如果我们已经能知道每头奶牛i能到的所有牧场，那么我们最终对所有牧场进行遍历，看看是不是所有奶牛都能到，统计这些牧场的总数即可。比如按照样本数据：

2 4 4 //2牛，4牧场，4条边
2 //牛1在2
3 //牛2在3
1 2
1 4
2 3
3 4

可以得到这样的图：

显然，这两头牛可以在3/4这两个点碰头。

• 牛1走到3号点，牛2不动。
• 牛1/2都走到4号点。

而牛能走到的点，可以用BFS来标记。

答案

思考

1. 我这里用了bitset<牧场数>[牛数]来快速标记某头牛i能否访问牧场j，这样设置和判定时可以不用遍历一个数组，而只要看对应的那一位是否标记即可。

// BFS中
if (!visited[next])
{
    visited[next] = true;
    reachable[cow].set(next);  // 设置对应位为1
    q.push(next);
}

//判定是否都能被访问：
if (!reachable[i][j])
{
    all_can_reach = false;
    break;
}