Coder-Strike 2014 Round1 - D. Giving Awards

適当に解いたけど想定解はなんなんだろう。
http://codeforces.com/contest/412/problem/D

問題

N個の頂点をソートしたい。
この時、(p番の直後にq番が来てはいけない)というルールがM個与えられる。
ルールに反しないソート結果を１つ答えよ。

解法

上記ルールについて、qに相当する数が多い、すなわち後に持ってくるのに制限が多い頂点から順に前から配置するとうまくいった。

以下のコードは必ずうまくいってるんだけど、うまくいかない例がないことは証明できるのかな。

int N,M;
set<int> E[100001];
int inin[100001];
int res[100001];
int vis[100001];
set<pair<int,int> > SI;
set<int> rev[100001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		inin[y-1]++;
	}
	FOR(i,N) SI.insert(make_pair(-inin[i],i));
	
	x=0;
	while(x<N) {
		ITR(it,SI) {
			int cur=it->second;
			if(x>0 && E[res[x-1]-1].find(cur)!=E[res[x-1]-1].end()) continue;
			SI.erase(it);
			vis[cur]++;
			res[x++]=cur+1;
			ITR(it2,E[cur]) {
				int tar=*it2;
				if(vis[tar]==0) {
					SI.erase(make_pair(-inin[tar],tar));
					inin[tar]--;
					SI.insert(make_pair(-inin[tar],tar));
				}
			}
			break;
		}
	}
	FOR(i,N) _P("%d ",res[i]);
	_P("\n");
}

まとめ

解答が「各頂点が出てくる順番」なのか「頂点の番号順」か一瞬混乱して無駄WAしてしまった。