题解：P1700 [USACO19OPEN] Milk Factory B

注意到 $1 \le N \le 100$，很小的数据范围给了我们很多可行的解法

1.搜索

建图，使用一个数组 $cnt$ 记录可以被几个点走到，从每个点开始 DFS/BFS，走到一个点就给 $cnt$ 中对应的点的数量 $+1$，最后从小到大扫一遍 $cnt$ 数组，如果一个点能被走到的数量为 $N - 1$ 则输出这个点，没有输出 $-1$。

抑或是反向建图，然后枚举每个点开始 DFS/BFS，走到了就给这个点标记为true，如果每一个点都被标记为true，输出对应的点；如果没有任何一个点可以满足，输出 $-1$。

时间复杂度都是 $O(N \times (N + M))$，约为 $O(N^2)$。

题解区全是这样的，代码就不贴了。

2.出度统计

暴力搜索在题目的范围里确实可过，可如果 $N$ 的范围扩大到 $1 \le N \le 10^6$，该怎么办呢？

题目中给出“有 $N$ 个点和 $N-1$ 条边”，在保证连通的基础下，可以得到这个图里不可能出现环。

也就是说，这个图的基底是一棵树。

因此，如果一个工厂 $u$ 有一条传送带指向 $v$（即 $u \to v$，出度 $>0$），那就意味着 $v$ 不可能有指向 $u$ 的传送带，也就是说，$u$ 不可能是可行的工厂了。

可得满足题意的工厂的要求：必须没有边指向其他点。也就是说，它的出度必须为 $0$。

同时，考虑唯一性验证：如果图中有两个及以上出度为 $0$ 的工厂（例如 $A \leftarrow B \rightarrow C$，A和C出度均为 $0$），此时没有任何一个工厂可以满足题意，故输出 $-1$ 报告无解。

这样做甚至不需要存图，统计一下出度并输出就可以，时间复杂度和空间复杂度都可以做到 $O(N)$。

代码如下：

#include <iostream>
using namespace std;

int deg[110], n, u, v;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;

    // 读入边，计算入度
    for(int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        // u -> v 表示 u 有一条传送带指向 v
        // 既然 u 有传送带去向别处，u 就不可能是最终的终点
        deg[u]++; 
    }

    int ans = -1; 
    for(int i = 1; i <= n; i++) {
        // 遍历寻找出度为 0 的点
        if(deg[i] == 0) {
            if(ans == -1) {
                // 找到了第一个出度为 0 的点，记录下来
                ans = i;
            } else {
                // 如果之前已经找到过一个出度为 0 的点，说明至少有两个点出度为0，此时无解
                cout << -1;
                return 0;
            }
        }
    }

    // 输出结果，ans 初始为 -1，如果没找到或唯一找到都会正确输出
    cout << ans;

    return 0;
}

AC记录

求赞qwq