T1
显然我们选择的点度数为2。
考虑若答案为Yes
,则原图最多有5个度数为2的点。多于5个直接判为No
。
因此可以枚举所有度数为2的点,暴力判断以该点为根,两个儿子的子树是否为菊花图。这是简单的,因为树为菊花图当且仅当点数不超过2或者一度点的个数等于点数-1。
时间复杂度 \(O(n)\)。
T2
考虑图中是否存在一条边 \((u,v)\),使得存在与 \(u\) 相邻的点 \(x(x\neq v)\) 和与 \(v\) 相邻的点 \(y(y\neq u)\),\(x\) 可以等于 \(y\)。
若存在,则只有 \(u,v,x,y\) 可能是混沌点,因为它们构成长度为3的链或环,不可能是菊花的一部分。
接下来,只要暴力考虑这几个点是否为混沌点。用并查集维护连通块大小和一度点个数即可,出现环即不合法。
如果这几个点都不合法,则图中没有混沌点。
若不存在,则原图就是一个“菊花森林”,所有点都是混沌点。
时间复杂度 \(O(n\alpha(n))\)。