Codeforces #694 Div1 D. Strange Housing

D問題の割にC問題よりだいぶすんなり。
https://codeforces.com/contest/1470/problem/D

問題

無向グラフが与えられる。
以下の条件を満たす頂点の選び方があれば、一例を示せ。

• 選んだ頂点同士は隣接しない。
• 片側が選択された頂点であるような辺のみを考えた場合、全頂点は連結する。

解法

まず元々連結でない場合は不可。
そうでない場合、以下の要領で点を選ぼう。

• DFS順で木を探索し、通った順に選択することを考える。
• ただし、各頂点において子頂点をたどる前に先に全隣接点をチェックし、選択済みの点が隣接するなら、今いる頂点は選択対象外とする。
• 改めてDFSで子頂点をたどる。

int T,N,M;
vector<int> E[303030];
int vis[303030]; //0-notyet 1-color 2-uncolor

void dfs(int cur) {
	if(vis[cur]) return;
	vis[cur]=1;
	FORR(e,E[cur]) if(vis[e]==1) vis[cur]=2;
	FORR(e,E[cur]) if(vis[e]==0) dfs(e);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		FOR(i,N) {
			E[i].clear();
			vis[i]=0;
		}
		FOR(i,M) {
			scanf("%d%d",&x,&y);
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		dfs(0);
		vector<int> C;
		FOR(i,N) {
			if(vis[i]==0) break;
			if(vis[i]==1) C.push_back(i+1);
		}
		if(i<N) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
			cout<<C.size()<<endl;
			FORR(v,C) cout<<v<<" ";
			cout<<endl;
		}
		
	}
		
}

まとめ

B問題とかに置かれてたらもっと解かれてるだろうな。