CF518 Div2 C - Colored Rooks

こんなしょうもない構築が解けなくてまたdiv1に戻れなかった
もう深夜のコンテストはレート落ちるの覚悟で出るべきかな・・

問題

色がn個あり、m個のペア(a[i],b[i])も与えられる
10^9 * 10^9のチェス盤があり、好きな位置にルークを最大5000個置くことができる
各ルークには色を塗る必要がある
↓の条件を全て満たすようなルークの置き方とそれぞれの色の組み合わせを1つ求めよ
1) n個の色それぞれで塗られているルークが少なくとも1つずつある
2) 同じ色のルークは連結である
3) 色aのルークの集合と色bの集合は、ペア(a,b)が存在するときのみ連結である
あるルークの集合が連結であるというのは、どのルークからも同じ集合のルーク上のみを通って同じ集合の任意のルークに辿り着けることを表す

1 <= n <= 100
0 <= m <= min(1000, n(n+1)/2)
答えは必ず1つ以上存在する

解法

まず色iのルークを座標(i,i)に1つ置く これで条件1はクリア
次に各ペアを1個ずつ見ていき、色a[i]のルークを(r+1,a[i])、b[i]を(r+1,b[i])に置く
(r: ルークが1個以上置かれている列のうち最も右の列のx座標)
こうすることで条件2,3を破らないようにペアを全て連結にすることができる

int n, m, a, b, r;
vector<pair<int,int> > res[111];

signed main() {
	cin >> n >> m;
	reps(i,1,n+1) res[i].push_back({i,i});
	r = n+1;
	rep(i,m) {
		cin >> a >> b;
		res[a].push_back({r,a}), res[b].push_back({r++,b});
	}
	reps(i,1,n+1) {
		cout << res[i].size() << endl;
		each(j,res[i]) cout << j.first << ' ' << j.second << endl;
	}
}

http://codeforces.com/contest/1068/problem/C