Codeforces #181 Div2 B "Coach"
問題
http://codeforces.com/contest/300/problem/B
訳
プログラミングのコーチはn人の生徒を受け持っている。
nは3で割り切れる事が分かっている。
生徒たちには1~nの番号がつけられている事を前提とする。
全国大学プログラミングコンテストを控えているので、
コーチは生徒たちを3人グループにわけようと考えている。
いくつかの生徒のペアは、同じチームになりたいと思っている。
生徒iが生徒jと同じチームになりたいと思っていれば、
生徒jも生徒iと同じチームになりたいと思っているようである。
コーチはコンテストでよい結果を出すために、
生徒iが生徒jと一緒になりたいと思っているならば、
生徒iと生徒jと同じチームにしようと考えている。
このようにして分割するとき、
分割後の各グループの生徒番号を出力せよ。
制約
3 <= n <= 48
0 <= ペア数 <= n * (n - 1) / 2
考えた事
Union-Find木でペアになりたい同士でグループ分けしていく。
各グループの人数が4以上になった時点でムリ!
人数が2人のグループは、ぼっちの生徒を補充しなくてはならない。
2人のグループの数 > ぼっちの生徒数となった時点でムリ!
あとは、
3人グループを出力
2人グループにぼっちの生徒を足して出力
残ったぼっちを出力すればよい
ソースコード
int N, M; int p[55]; // aの親は誰ですか? int find( int a ){ if( a == p[a] ) return a; return p[a] = find( p[a] ); } // a, bを併合する void uni( int a, int b ){ a = find( a ); b = find( b ); p[b] = a; } int main() { cin >> N >> M; for( int i = 1; i <= N; i++ ){ p[i] = i; } for( int i = 0; i < M; i++ ){ int a, b; cin >> a >> b; uni( a, b ); } int cnt[55]; memset( cnt, 0, sizeof(cnt) ); for( int i = 1; i <= N; i++ ){ cnt[find(i)]++; } int needOne = 0; int one = 0; bool ok = true; for( int i = 1; i <= N; i++ ){ if( cnt[i] > 3 ){ ok = false; break; } if( cnt[i] == 1 ) one++; if( cnt[i] == 2 ) needOne++; } // 二人グループ > ぼっち // もしくは 4人以上のグループがあったらだめ if( needOne > one || !ok ){ cout << -1 << endl; return 0; } bool chk[ 55 ]; memset( chk, false, sizeof(chk) ); for( int i = 1; i <= N; i++ ){ // 3人グループを出力 if( cnt[i] == 3 ){ for( int j = 1, c = 1; j <= N; j++ ){ if( find(j) != i ) continue; chk[j] = true; printf( "%d%c", j, (c % 3 == 0 ? '\n' : ' ' ) ); c++; } } // 2人グループを出力 if( cnt[i] == 2 ){ for( int j = 1; j <= N; j++ ){ if( find(j) != i ) continue; chk[j] = true; printf( "%d ", j ); } // ぼっち追加 for( int j = 1; j <= N; j++ ){ if( cnt[j] != 1 || chk[j] ) continue; chk[j] = true; printf( "%d\n", j ); break; } } } // 残ったぼっちをチームを組ませて出力 for( int i = 1, c = 1; i <= N; i++ ){ if( chk[i] ) continue; printf( "%d%c", i, (c % 3 == 0 ? '\n' : ' ' ) ); c++; } }