关于今天CF-Div.2E WA on 17求助
  • 板块学术版
  • 楼主spdarkle
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/8 23:57
  • 上次更新2023/11/2 14:51:03
查看原帖
关于今天CF-Div.2E WA on 17求助
507718
spdarkle楼主2023/10/8 23:57
#include<bits/stdc++.h>
using namespace std;
#define N 1050505
#define int long long
int head[N],ver[N],n,nxt[N],tot,vis[N],abl[N],cir[N],c[N],dcc,a[N],num,V[N],col[N],siz[N],son[N],bg[N],dep[N];
void ad(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void add(int u,int v){
	ad(u,v);ad(v,u);	
}
vector<int>g;
void pai(int u){
	c[u]=dcc;g.push_back(u);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(!c[v])pai(v);
	}
}
void dfs(int u,int fa){
	siz[u]=1;int tag=0;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa||V[v])continue;
		dfs(v,u);siz[u]+=siz[v];son[u]++;dep[u]=max(dep[u],dep[v]);
		bg[u]=v;
		if(col[v]==1)tag=1;
	}
	if(!tag)col[u]=1;
	else col[u]=2;
	dep[u]++;
}
void get_circle(){
	for(auto x:g)vis[x]=0;
	int u=g[0];
	while(!vis[u]){
		vis[u]=1;u=a[u];
	}
	for(auto x:g)vis[x]=0;
	int num=0;
	while(!vis[u])cir[++num]=u,vis[u]=1,u=a[u];
	for(int i=1;i<=num;i++)V[cir[i]]=1;
	for(int i=1;i<=num;i++)dfs(cir[i],0);
	for(int i=1;i<=num;i++)cir[num+i]=cir[i]; 
	if(num==1&&col[cir[1]]==1){
		cout<<"-1\n";
		exit(0);
	}
	for(int i=1;i<=num;i++){
		if(col[cir[i]]==1&&col[cir[i+1]]==1){
			col[cir[i+1]]=2;
		}
	}
	if(num%2==0)return ;
	for(int i=1;i<=num;i++){
		if(col[cir[i]]==2){
			int tag=0,u=cir[i];
			for(int i=head[u];i;i=nxt[i]){
				int v=ver[i];if(v==a[u])continue;
				if(V[v]==0)tag=1;
				if(col[v]==1)tag=1;
			}
			if(tag==0&&num!=2){
				cout<<"-1\n";
				exit(0);
			}
		}
	}
}
signed main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		add(a[i],i);
	}
	for(int i=1;i<=n;i++){
		if(!c[i]){
			++dcc;g.clear();
			pai(i);
			get_circle();
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)if(col[i]==1)++cnt;
	cout<<cnt<<"\n";
	for(int i=1;i<=n;i++)if(col[i]==1)cout<<a[i]<<" ";
}
2023/10/8 23:57
加载中...