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