codeforces 1325F
题目链接
题意给一个n个点m条边的无向联通图，要求在图上要么找出一个至少ceil(sqrt(n))个点的环，要么找出一个cail(sqrt(n))个点的独立集
数据范围n≤1e5 m≤2e5n\le 1e5~~~~~m\le 2e5n≤1e5 m≤2e5
解法dfs树：
首先考虑找环，就是对于一条返祖边(u,v),dep[u]>dep[v]，环的大小就是dep[u]-dep[v]+1,然后如果没有满足条件的环，考虑找独立集
我考场上找独立集的方法比较不靠谱：先根据每个点在dfs树上的深度奇偶分类，并且放到不同的答案集合中。然后对于一条返祖边，如果两端的点深度奇偶性相同，且两个点都在答案集合中，那么删除其中深度较小的（较大的同样可以）。最后看两个答案集合哪个满足条件。这个算法显然取不出最大独立集。（这个解法是有问题的，hack数据：
10 17
1 3
3 5
5 7
7 9
2 4
4 6
6 8
8 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
这个数据虽然有一个大环，但是dfs树其实并不能找出所有的环，会变成一条链上有很多不满足条件的小环，然后此时再奇偶分组，就凑不出足够大小的独立集
）
而题解做法的正确性证明是一个点最多有ceil(sqrt(n))-2条返祖边，所以如果只考虑这个点和这个点的返祖边， 那么一个点最多能删除ceil(sqrt(n))-2个点，加上自己就是每ceil(sqrt(n))-1个点中必然有一个加入了答案集合，于是可以选
n/(ceil(sqrt(n))-1)>=n/floor(sqrt(n))>=ceil(sqrt(n))个点
所以如果必须从叶子向根贪心才正确，而我考场的代码是从根向叶子贪心，说来搞笑，如果不加奇偶分组，直接从根向叶子贪心是过不了的（显然，一个菊花就hack了）
考场代码
#include
using namespace std;
const int maxn=2e5+5;
inline int read(){
char c=getchar();int t=0,f=1;
while((!isdigit(c))&&(c!=EOF)){if(c=='-')f=-1;c=getchar();}
while((isdigit(c))&&(c!=EOF)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
return t*f;
}
int n,m;
struct edge{
int v,p;
}e[maxn<=lim){
ans=2;
int tmp=st[top];
do{
out[++tot]=tmp;
top--;
tmp=st[top];
}while(tmp!=v&&top);
out[++tot]=v;
return ;
}
}
else{
vis[v]=1;
dep[v]=dep[u]+1;
dfs(v);
if(ans)return ;
}
}
top--;
}
int col[maxn],cur;
set s[2];
int sum[2],qaq[maxn];
void get(int u){
st[++top]=u;
for(int i=h[u];i;i=e[i].p){
int v=e[i].v;
if(vis[v]){
if((dep[u]-dep[v])&1)continue;
if(qaq[u]&&qaq[v]){
qaq[v]=0;
s[dep[v]&1].erase(v);
sum[dep[v]&1]--;
}
/* else{
if(qaq[v]){
qaq[v]=0;
s[dep[v]&1].erase(v);
sum[dep[v]&1]--;
}
}*/
}
else{
vis[v]=1;
get(v);
}
}
}
signed main(){
n=read();m=read();
for(;lim*lim<n;lim++);
for(int i=1;i<=m;i++){
int a=read(),b=read();
add(a,b);
}vis[1]=1;
dfs(1);
if(ans){
printf("%d\n%d\n",ans,tot);
for(int i=1;i<=tot;i++)printf("%d ",out[i]);
return 0;
}
printf("1\n");
memset(vis,0,sizeof(vis));
for(int i=1;i=lim){
for(int i=1;i<=lim;i++){
set::iterator it=s[0].begin();
printf("%d ",*it);
s[0].erase(it);
}
return 0;
}
else if(sum[1]>=lim){
for(int i=1;i<=lim;i++){
set::iterator it=s[1].begin();
printf("%d ",*it);
s[1].erase(it);
}
return 0;
}
return 0;
}
重新修改过的代码
#include
using namespace std;
const int maxn=2e5+5;
inline int read(){
char c=getchar();int t=0,f=1;
while((!isdigit(c))&&(c!=EOF)){if(c=='-')f=-1;c=getchar();}
while((isdigit(c))&&(c!=EOF)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
return t*f;
}
int n,m;
struct edge{
int v,p;
}e[maxn<=lim){
ans=2;
int tmp=st[top];
do{
out[++tot]=tmp;
top--;
tmp=st[top];
}while(tmp!=v&&top);
out[++tot]=v;
return ;
}
}
else{
vis[v]=1;
dep[v]=dep[u]+1;
dfs(v);
if(ans)return ;
}
}
top--;
}
int col[maxn],cur;
set s;
int qaq[maxn];
void get(int u){
for(int i=h[u];i;i=e[i].p){
int v=e[i].v;
if(dep[v]==dep[u]+1)
get(v);
}
if(qaq[u]){
for(int i=h[u];i;i=e[i].p){
int v=e[i].v;
if(qaq[v]){
qaq[v]=0;s.erase(v);
}
}
}
}
signed main(){
//freopen("6.in","r",stdin);
//freopen("6.out","w",stdout);
n=read();m=read();
for(;lim*lim<n;lim++);
for(int i=1;i<=m;i++){
int a=read(),b=read();
add(a,b);
}vis[1]=1;
dfs(1);
if(ans){
printf("%d\n%d\n",ans,tot);
for(int i=1;i<=tot;i++)printf("%d ",out[i]);
return 0;
}
printf("1\n");
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
s.insert(i);qaq[i]=1;
}
vis[1]=1;
get(1);
for(int i=1;i<=lim;i++){
set::iterator it=s.begin();
printf("%d ",*it);
s.erase(it);
}
return 0;
}
作者：新笑雨
