Codeforces #959 : F. Stardew Valley

ここまではどうにか本番中に解けた。
https://codeforces.com/contest/1994/problem/F

問題

N点M辺の無向グラフが与えられる。
各辺は、NPCがいる辺といない辺がある。
このグラフは、NPCがいる辺だけで連結であることが保証される。

NPCがいる辺をすべて含む、同じ辺を2回以上通らない閉路が存在するか、するなら一例を示せ。

解法

NPCがいる辺だけでグラフが連結なのは確定。
あとは各点の次数が偶数となるようにできれば、オイラー閉路を構築できる。
DFSの要領で、葉から順にNPCがいない辺を必要に応じて追加し、各点の次数を偶数にしよう。

int T;
int N,M;
vector<pair<int,int>> Es;
int NE[505050];
vector<int> E[505050];
int L[505050];
int vis[505050];
int NP[505050];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
	void dump(int num=um) { //グループ分けした配列を作る
		int i;
		FOR(i,num) G[i].clear();
		FOR(i,num) G[operator[](i)].push_back(i);
	}
};
UF<505050> uf;

template<int MV> class UndirectedEulerPath {
public:
	int NV;
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }

	
	void init(int NV){
		this->NV=NV;
		for(int i=0;i<NV;i++) E[i].clear();
		path.clear();
	}
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	bool GetPath(int root=-1) { // 開始地点を探し、条件を満たすか判定
		int fo=-1,odd=0,i,np=0;
		assert(NV);
		FOR(i,NV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
		}
		//閉路なら奇数を許容しないようにしておく
		if(odd!=0 && odd!=2) return false;
		if(root==-1) {
			if(odd) {
				root=fo;
			}
			else {
				FOR(i,NV) if(E[i].size()) root=i;
			}
		}
		else {
			if(odd==2&&E[root].size()%2==0) return false;
		}
		dfs(root);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}
};

UndirectedEulerPath<501000> uep;

void dfs(int cur) {
	if(vis[cur]) return;
	vis[cur]=1;
	if(L[cur]) {
		NP[cur]=1;
	}
	else {
		NP[cur]=0;
	}
	
	FORR(e,E[cur]) if(vis[e]==0) {
		dfs(e);
		if(NP[e]) {
			Es.push_back({e,cur});
			NP[cur]^=1;
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		uf.reinit(N);
		Es.clear();
		FOR(i,N) {
			E[i].clear();
			NE[i]=0;
			vis[i]=0;
		}
		FOR(i,M) {
			cin>>x>>y>>k;
			x--,y--;
			if(k==0) {
				if(uf[x]!=uf[y]) {
					E[x].push_back(y);
					E[y].push_back(x);
					uf(x,y);
				}
			}
			else {
				Es.push_back({x,y});
				NE[x]++;
				NE[y]++;
			}
		}
		FOR(i,N) {
			L[i]=NE[i]%2;
		}
		FOR(i,N) if(vis[i]==0) {
			dfs(i);
			if(NP[i]) break;
		}
		if(i!=N) {
			cout<<"NO"<<endl;
			continue;
		}
		
		uep.init(N);
		FORR2(a,b,Es) uep.add_path(a,b);
		uep.GetPath(-1);
		
		cout<<"YES"<<endl;
		cout<<uep.path.size()-1<<endl;
		FORR(p,uep.path) cout<<p+1<<" ";
		cout<<endl;
		
	}
		
}

まとめ

コード量は多いけど、考え方はさほど難しくない。