Codeforces #181 Div2 B "Coach"

問題

http://codeforces.com/contest/300/problem/B

訳

プログラミングのコーチはn人の生徒を受け持っている。
nは3で割り切れる事が分かっている。
生徒たちには1～nの番号がつけられている事を前提とする。

全国大学プログラミングコンテストを控えているので、
コーチは生徒たちを３人グループにわけようと考えている。
いくつかの生徒のペアは、同じチームになりたいと思っている。
生徒iが生徒jと同じチームになりたいと思っていれば、
生徒jも生徒iと同じチームになりたいと思っているようである。
コーチはコンテストでよい結果を出すために、
生徒iが生徒jと一緒になりたいと思っているならば、
生徒iと生徒jと同じチームにしようと考えている。

このようにして分割するとき、
分割後の各グループの生徒番号を出力せよ。

制約

3 <= n <= 48
0 <= ペア数 <= n * (n - 1) / 2

考えた事

Union-Find木でペアになりたい同士でグループ分けしていく。
各グループの人数が4以上になった時点でムリ！
人数が２人のグループは、ぼっちの生徒を補充しなくてはならない。
２人のグループの数 > ぼっちの生徒数となった時点でムリ！

あとは、
３人グループを出力
２人グループにぼっちの生徒を足して出力
残ったぼっちを出力すればよい

ソースコード

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++;
    }

    // 二人グループ > ぼっち
    // もしくは ４人以上のグループがあったらだめ
    if( needOne > one || !ok ){
        cout << -1 << endl;
        return 0;
    }

    bool chk[ 55 ];
    memset( chk, false, sizeof(chk) );
    for( int i = 1; i <= N; i++ ){
        // ３人グループを出力
        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++;
            }
        }
        // ２人グループを出力
        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++;
    }
}