Codeforces #576 Div1 C. Matching vs Independent Set

うーん、こういうの苦手。
https://codeforces.com/contest/1198/problem/C

問題

3N頂点M辺の無向グラフが与えられる。
以下のいずれかを構築できれば、それを答えよ。

• M辺中、互いに独立なN辺、すなわち端点を共有しない辺がある
• 3N点中、互いに独立なN点、すなわち辺で結ばれない頂点がある。

解法

必ずどちらかは構成できる。
まず前者は、貪欲に先頭から「両端がいずれも使われていない辺」を取っていき、N辺取れればそれで良い。
前者が達成できない場合、それらの辺は2N個以下の頂点しか使わないので、残りN個の頂点を答えればよい。

int T;
int N,M;
int did[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		N*=3;
		
		FOR(i,N) did[i]=0;
		
		vector<int> C;
		FOR(i,M) {
			int U,V;
			scanf("%d%d",&U,&V);
			U--;
			V--;
			
			if(did[U]==0 && did[V]==0) {
				C.push_back(i+1);
				did[U]=did[V]=1;
			}
		}
		
		if(C.size()>=N/3) {
			_P("Matching\n");
			FOR(i,N/3) _P("%d ",C[i]);
			_P("\n");
			continue;
		}
		C.clear();
		FOR(i,N) if(did[i]==0) C.push_back(i+1);
		_P("IndSet\n");
		FOR(i,N/3) _P("%d ",C[i]);
		_P("\n");
	}
}

まとめ

複雑に考えすぎた。うーん。