Codeforces ECR #105 : F. Delete The Edges

考察パートをクリアできればあとはもうすぐ。
https://codeforces.com/contest/1494/problem/F

問題

N点M辺の無向グラフが与えられる。
任意の点にコマを置き、そこから以下の手順で辺を消しながらコマを移動させることを考える。

• 最初は、任意の辺を選び辺に沿ってコマを移動させる。その際、通過した辺を消す。
• 途中、モードシフトを1回だけ行うことができる。
• モードシフト後は、奇数回目の移動では辺が消え、偶数回目の移動では辺が消えない。

全辺を消せる経路が存在するなら、それを判定せよ。

解法

モードシフト後に辺を消しきれるグラフは、実はスターグラフに限定される。
また、その時の開始地点はスターグラフの中央でなければならない。

モードシフト前最後の遷移u→vを総当たりすることを考える。
vでモードシフト後に残るグラフはスターグラフでないといけないことから、u以外のvの隣接点wに対し、u-w間の辺のみモードシフト前後のどちらに経由するかの選択肢が生じる。
そこで、モードシフト前のwの次数が偶数になるように、モードシフト前後いずれに通過するように選ぼう。

あとは、モードシフト前に消すべき辺がvを端点とするオイラーパスを持つか判定すればよい。

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) {
		E[x].insert(y); E[y].insert(x);
	}
	
	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;
		FOR(i,MV) {
			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) {
			root=odd?fo:0;
		}
		else {
			if(odd==2&&E[root].size()%2==0) return false;
		}
		dfs(root);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}

};

int N,M;
vector<pair<int,int>> V;
int path[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	MINUS(path);
	FOR(i,M) {
		cin>>x>>y;
		V.push_back({x,y});
	}
	
	
	for(i=1;i<=N;i++) {
		V.push_back({i,0});
		FORR(v,V) if(v.first==i||v.second==i) {
			UndirectedEulerPath<3030> uep2;
			int C[3030]={};
			int ne=0;
			FORR(w,V) if(w.first!=i&&w.second!=i) {
				C[w.first]++;
				C[w.second]++;
				uep2.add_path(w.first,w.second);
				ne++;
			}
			vector<int> left;
			FORR(w,V) if(w.first==i||w.second==i) {
				if(w.first==0||w.second==0) continue;
				x=w.first+w.second-i;
				if(C[x]%2!=(v==w)) C[i]++,C[x]++,uep2.add_path(i,x),ne++;
				else left.push_back(x);
			}
			
			if(uep2.GetPath(i)) {
				auto p=uep2.path;
				reverse(ALL(p));
				if(left.size()) {
					p.push_back(-1);
					FORR(v,left) p.push_back(v),p.push_back(i);
				}
				
				cout<<p.size()<<endl;
				FORR(a,p) cout<<a<<" ";
				cout<<endl;
				return;
				
			}
		}
		V.pop_back();
	}
	cout<<0<<endl;
	
	
}

まとめ

スターグラフになることに気付かない時点で、その先何もできない…。