USACO 牛奶加工厂反向建图 DFS题解复盘基本信息项目内容题目编号、来源USACO / 牛奶加工厂训练层级A DFS / 图论知识版块DFS、反向建图、有向图可达性解题前・关键信号识别维度分析目标、约束、底层结构目标N 个点N-1 条有向边求是否存在一个点 i使得从其他所有点都能到达 i约束N ≤ 100底层结构有向图判断是否存在点 i 满足所有点都能到达它。数据规模N ≤ 100O(N²) 暴力 DFS 完全可行。候选算法和依据反向建图 DFS依据判断「所有点都能到达 i」等价于「从 i 出发能到达所有点」因此可以反向建边从 i 开始 DFS若能访问全部 N 个点则 i 满足条件。复杂度预判时间复杂度 O(N²)每次 DFS O(NE)最多执行 N 次空间复杂度 O(NE)。解题后・外化复盘维度内容实现结构 / 核心思路第一步将 N 条有向边a → b反向存储为b → a第二步枚举每个点 i1 到 N从 i 开始 DFS第三步若某次 DFS 能访问全部 N 个节点则输出 i 并结束第四步若枚举完所有点都没有输出 -1。核心思想正向图中「所有点都能到 i」等价于反向图中「i 能到所有点」。错因回溯1. 正向建图后从每个点出发判断能否到 i需要 N 次 DFS复杂度 O(N²) 但代码更复杂2. 反向建图后只需从 i 出发 DFS能访问全部 N 个点即满足条件3. 忘记清空visited数组了。边界和易错点1. 建图时输入是a b表示a → b反向存储为v[b].push_back(a)2. 每次 DFS 前要清空 visited 数组用memset并重置 Count 为 03. 输出最小的满足条件的 i从小到大枚举即可4. 树有 N-1 条边保证连通但方向可能无法全连通。下次看到什么信号我应该想到这个方法看到「判断所有点是否能到达某个点」用反向建图转化为「从该点出发能否到达所有点」看到「有向图 可达性」用 DFS / BFS。AC 完整代码#includeiostream#includealgorithm#includecstring#includevectorusingnamespacestd;intn;vectorintv[105];boolvisited[105];intCount;voiddfs(intcurrent){visited[current]true;Count;for(intnext:v[current]){if(!visited[next]){dfs(next);}}}intmain(){cinn;for(inti0;in-1;i){inta,b;cinab;v[b].push_back(a);}for(inti1;in;i){Count0;memset(visited,false,sizeof(visited));dfs(i);if(Countn){coutiendl;return0;}}cout-1endl;return0;}