0w1

CFR 277 1A. Learning Languages ( Union Find )

Problem - 277A - Codeforces
很顯然可以將每個人分別看成點,兩個不同分量若各自有一個人能說共同語言,就能把兩個分量所有點合併。假設所有人都會說至少一種語言,答案就是分量的數量減一。如果有人不會任何語言,那麼他們都必須學一種語言,所以得另外加上這些人的數量。最後要注意,如果所有人都不會說任何語言,那麼答案顯然會是n,但要特別處理。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int MAXM = 100 + 2;

int n, m;
int sz[ MAXN ];
int lang[ MAXN ][ MAXM ];
set< int > lang_set[ MAXN ];
int zero_cnt;

struct UnionFind{
    int fa[ MAXN ];
    void init( int _n ){
        for( int i = 0; i < _n; ++i )
            fa[ i ] = i;
    }
    int find( int x ){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); }
    bool unite( int x, int y ){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b; return true;
    }
} uf;

int main(){
    scanf("%d%d", &n, &m);
    for( int i = 0; i < n; ++i ){
        scanf("%d", sz + i);
        for( int j = 0; j < sz[ i ]; ++j ){
            scanf("%d", &lang[ i ][ j ]);
            lang_set[ i ].insert( lang[ i ][ j ] );
        }
    }
    uf.init( n );
    for( int i = 0; i < n; ++i ){
        if( sz[ i ] == 0 ){
            ++zero_cnt;
            continue;
        }
        for( int j = 0; j < n; ++j ) if( i != j )
            for( int k = 0; k < sz[ i ]; ++k )
                if( lang_set[ j ].count( lang[ i ][ k ] ) ){
                    uf.unite( i, j );
                    break;
                }
    }
    if( zero_cnt == n ) printf("%d\n", n);
    else{
        set< int > cc;
        for( int i = 0; i < n; ++i ) if( sz[ i ] > 0 )
            cc.insert( uf.find( i ) );
        printf("%d\n", zero_cnt + (int)cc.size() - 1);
    }
    return 0;
}