构造小结
构造题训一道不会一道。
先从萌萌题做起。
CF1817B Fish Graph
数据范围只有 \(2000\)。
考虑枚举度数大于等于 \(4\) 的点 \(u\)，然后搜索点 \(u\) 是否在一个环上，设 \(zu_i\) 为点 \(i\) 的祖先（即点 \(i\) 可以通往 点 \(u\) 的哪个邻结点），暴力 \(\tt{bfs}\) 并记录前驱即可，时间复杂度 \(O(nm)\)。
跑点双可以做到 \(O(n)\)。
构造题训一道不会一道。
先从萌萌题做起。
数据范围只有 \(2000\)。
考虑枚举度数大于等于 \(4\) 的点 \(u\)，然后搜索点 \(u\) 是否在一个环上，设 \(zu_i\) 为点 \(i\) 的祖先（即点 \(i\) 可以通往 点 \(u\) 的哪个邻结点），暴力 \(\tt{bfs}\) 并记录前驱即可，时间复杂度 \(O(nm)\)。
跑点双可以做到 \(O(n)\)。