abc345f求调
查看原帖
abc345f求调
602009
OIer_ljb楼主2024/3/20 20:54

RT,错了06_corner_01.txt

#include<cstdio>
#include<cstring>
#define ll long long
const int N=3e5+5;
int n,m,k,u,v,fa[N],ord[N],cnt,bj[N],q[N],col[N],id[N],ans,sum,qq[N<<1];
int nt[N<<1],to[N<<1],fi[N],tot=1;
inline void add(int x,int y){++tot;nt[tot]=fi[x];to[tot]=y;fi[x]=tot;}
inline int max(int x,int y){return x>y?x:y;} 
void bfs()
{
	for(int i=1;i<=n;++i)
	{
		if(bj[i]==0)
		{
			int h=0,t=1;
			q[t]=i;bj[i]=1;
			while(h<t)
			{
				++h;int x=q[h];++cnt;ord[cnt]=x;
				for(int i=fi[x];i;i=nt[i])
				{
					int y=to[i];
					if(bj[y]==0)fa[y]=x,id[y]=i/2,bj[y]=1,++t,q[t]=y;
				}	
			}	
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	if(k==0){printf("Yes");return 0;}
	if(k&1)printf("No");
	else
	{
		for(int i=1;i<=m;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
		bfs();
		for(int i=n;i;--i)
		{
			if(id[ord[i]]&&col[ord[i]]==0)
			{
				col[ord[i]]=1;++ans;++sum,qq[sum]=id[ord[i]];col[fa[ord[i]]]^=1;
				if(col[fa[ord[i]]])++ans;
				else --ans;
				if(ans==k)break;
			}
		}
		if(ans==k)
		{
			printf("Yes\n");
			printf("%d\n",sum);
			for(int i=1;i<=sum;++i)printf("%d ",qq[i]);	
		}
		else printf("No\n");
	}
}
2024/3/20 20:54
加载中...