Codeforces Global Round 8 : E. Ski Accidents

ここ数回CFも調子悪いな。
https://codeforces.com/contest/1368/problem/E

問題

DAGを成すN頂点の有向グラフが与えられる。
各点の出次数は2以下である。

ここから4*N/7個以下の点を取り除き、長さ2のパスができないようにせよ。

解法

根からどん欲に、長さ２のパスができそうになったらその点を取り除く、でよい。

int T;
int N,M;
vector<int> E[202020];
int mask[202020];

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();
			mask[i]=0;
		}
		int K=4*N/7;
		
		FOR(i,M) {
			cin>>x>>y;
			x--,y--;
			E[x].push_back(y);
		}
		
		vector<int> cand;
		FOR(i,N) {
			if(mask[i]&2) {
				cand.push_back(i+1);
			}
			else if(mask[i]&1) {
				FORR(e,E[i]) mask[e]|=2;
			}
			else {
				FORR(e,E[i]) mask[e]|=1;
			}
		}
		
		assert(cand.size()<=K);
		cout<<cand.size()<<endl;
		FORR(c,cand) cout<<c<<" ";
		cout<<endl;
		
	}
}

まとめ

これ自信もって出せる気がしないなぁ。