Codeforces #869 : Div1 B. Fish Graph

ダメダメだった回。
https://codeforces.com/contest/1817/problem/B

問題

ある無向グラフがFish Graphであるとは、1つのシンプルな閉路のうち、1つの点に追加で2つの辺が追加されたものをいう。

無向グラフが与えられるので、その部分グラフでFish Graphとなるものがあればそれを答えよ。

解法

2つの辺が追加される点を総当たりしよう。
辺が4つ以上の点vに対し、vを含むシンプルな閉路を見つけられれば、閉路に含まれない2本の辺を追加することで条件を満たせる。

int T,N,M;
vector<int> E[2020];
int vis[2020];
vector<int> R;
vector<int> ok;
set<int> SE[2020];
void dfs(int cur,int pre,int tar) {
	if(ok.size()) return;
	if(cur==tar&&pre!=cur) {
		ok=R;
		return;
	}
	if(vis[cur]) {
		return;
	}
	vis[cur]=1;
	R.push_back(cur);
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,tar);
	R.pop_back();
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) E[i].clear(),SE[i].clear();
		ok.clear();
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
			SE[x-1].insert(y-1);
			SE[y-1].insert(x-1);
		}
		vector<pair<int,int>> ret;
		FOR(i,N) if(E[i].size()>=4) {
			ZERO(vis);
			R.clear();
			dfs(i,i,i);
			if(ok.empty()) continue;
			
			for(j=2;j<ok.size();j++) {
				if(SE[i].count(ok[j])) {
					while(ok.size()>j+1) ok.pop_back();
					break;
				}
			}
			FOR(j,ok.size()) ret.push_back({ok[j],ok[(j+1)%ok.size()]});
			int lef=2;
			FORR(e,E[i]) if(lef&&e!=ok[1]&&e!=ok.back()) {
				ret.push_back({i,e});
				lef--;
			}
			break;
		}
		
		if(ret.size()) {
			cout<<"YES"<<endl;
			cout<<ret.size()<<endl;
			FORR2(a,b,ret) cout<<a+1<<" "<<b+1<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
			
	}
}

まとめ

色々コーナーケースを踏んでしまい手間取った記憶がある。