选择个数应该大致为 $\frac 2 3 n,\frac 2 9 n,\cdots$。
并且对于一个图,如果可以从某个图变换 $x$ 次到达这个图,那么颜色大小至少为 $x+1$。
by Doqe @ 2024-04-16 15:09:00
另外,题解的 dfs 好像没有处理新边的端点相同的情况,不知道会不会在这种情况下出事。
by Doqe @ 2024-04-16 15:11:57
貌似找到 hack 了。
```
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>X;
int B[]={0,6,5,6,5,6,6,6,0};
int main()
{
freopen("w.in","w",stderr);
int z=1;
for(int i=1;B[i];++i)
{
for(int o=1;o<=z;++o)
{
for(int j=1;j<B[i];++j)
X.emplace_back(o,o+j*z);
}
z*=(B[i]);
}
//cout<<X.size()+1<<" "<<z<<endl;
cerr<<X.size()+1<<" "<<0<<endl;
for(auto k:X)cerr<<k.first<<" "<<k.second<<'\n';
cerr<<0.001<<endl;
}
```
使用此代码生成的数据在钦定颜色数为 $6$ 和 $7$ 的时候表现不一样。
by Doqe @ 2024-04-16 17:27:06