Codeforces Round #628 (Div. 2) 一道比较简单的 搜索 题。
题目链接:Codeforces 1325F。
系列题解:
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd;
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy;
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs;
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist;
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem;
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。
题目
原题
题意简述
给出一个 $n$ 个点 $m$ 条边的图,给你两个任务:
- 找一个有且只有 $\left\lceil\sqrt{n}\right\rceil$ 个点的独立集;
- 找一个至少有 $\left\lceil\sqrt{n}\right\rceil$ 个点的简单环;
任选一个完成。
数据范围
$$5\leq n\leq 10^5$$
$$n-1\leq m\leq 2\times 10^5$$
时空限制
见原题 pdf
文件。
题解
思路
考虑这样的做法,在图上 DFS,如果找到符合条件的环,则选择任务 $2$,然后输出,结束程序。
否则根据得到的信息找到满足条件的独立集即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=100000+5;
const int MAXM=200000+5;
int n,m;
int cnt,head[MAXN],to[MAXM<<1],Next[MAXM<<1];
int fa[MAXN],dep[MAXN];
inline void Add_Edge(reg int u,reg int v){
Next[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
return;
}
int tot;
int Q[MAXN];
bool vis[MAXN];
inline void DFS(reg int ID){
Q[++tot]=ID;
dep[ID]=dep[fa[ID]]+1;
for(reg int i=head[ID];i;i=Next[i])
if(!dep[to[i]]){
fa[to[i]]=ID;
DFS(to[i]);
}
else if(dep[to[i]]<dep[ID]){
reg int l=dep[ID]-dep[to[i]]+1;
if(l*l>=n){
printf("2\n%d\n",l);
for(reg int j=ID;j;j=fa[j]){
printf("%d%c",j,j==to[i]?'\n':' ');
if(j==to[i])
break;
}
exit(0);
}
}
return;
}
int main(void){
n=read(),m=read();
for(reg int i=1;i<=m;++i){
static int u,v;
u=read(),v=read();
Add_Edge(u,v);
Add_Edge(v,u);
}
DFS(1);
reg int l=1;
for(;l*l<n;++l);
reg int rem=l;
puts("1");
for(reg int i=n;i>=1;--i){
reg int x=Q[i];
if(vis[x])
continue;
--rem;
printf("%d%c",x,rem?' ':'\n');
if(!rem)
exit(0);
for(reg int j=0;j<=l-2;++j){
vis[x]=true;
x=fa[x];
}
}
return 0;
}
近期评论