Codeforces #170, Division 2, C : Learning Languages

問題文

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

概要

ある会社には n 人の従業員がおり、m 個の公用語がある。
一人の従業員に一つの言語を教えるコストが 1 である。
各社員が使える言語の情報が与えられるので、全ての社員が互いに（他の社員に通訳をさせてでも）話ができるようにするために必要な最小コストを求めよ。

解法

社員をノードとした無向グラフを考えます。
二人の社員が共通の言語を使える場合にその二者間にエッジを張ります。
このグラフに於いて、同一の連結成分に属する社員同士は話ができます。
また、エッジを一本追加することで、二つの連結成分を連結することができます。
このとき、どちらかの連結成分内で通じる言語を教えることで、コスト 1 にてエッジを追加できます。
従って、このグラフの連結成分の数 - 1 が答えとなります。
ただし、言語の数が全員 0 の場合は n です。

連結成分を数えるのは、BFS/DFS で頂点を塗りつぶしていけばよいです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

void dfs( const VVI &G, vector<bool> &used, int v )
{
	if ( used[v] )
	{
		return;
	}

	used[v] = true;

	FOR( next, G[v] )
	{
		dfs( G, used, next );
	}
	return;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, m;
	cin >> n >> m;

	bool allzero = true;

	VVI emp( n );
	FOR( lang, emp )
	{
		int k;
		cin >> k;
		lang.resize( k );
		allzero &= k == 0;
		FOR( l, lang )
		{
			cin >> l;
		}
		sort( ALL( lang ) );
	}

	VVI G( n );
	REP( i, 0, n )
	{
		REP( j, i + 1, n )
		{
			REP( l, 1, m + 1 )
			{
				if ( binary_search( ALL( emp[i] ), l ) && binary_search( ALL( emp[j] ), l ) )
				{
					G[i].PB( j );
					G[j].PB( i );
				}
			}
		}
	}

	vector<bool> used( n, false );
	int res = allzero ? 0 : -1;
	REP( i, 0, n )
	{
		if ( used[i] )
		{
			continue;
		}

		res++;
		dfs( G, used, i );
	}

	cout << res << endl;

	return 0;
}