USACO analysis
肖肖 |
09 Dec 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
⚠ 该解析描述需要进一步细化和具体实现
我们认为这条解析不够完善，如果你有更好的解析/更加详细的思路欢迎用微信发给mark或者以"USACO Solution"为主题发送到 286988023@qq.com题目
给出N个草地以及M头牛和每头牛的要求(某两块草地的品种相同或者不同),然后计算有多少种种植草地的方法
分析
我们可以使用两个UFDS分别记录相连的和不能相连的草地,接着将这两个UFDS合并,然后判断有多少个块是相互连接的方案数就是2^块数^
复杂度
O(n)首先合并所有的点需要分别遍历每个UFDS,最后求出一共有多少个块数就是枚举有多少个点复杂度O(n)
