Codeforces #170 Div2 C " Learning Languages"
問題
ある会社には社員がN人いる。
この会社は国際的なので、M個の言語が公用語として認められている。
社員は予めいくつかの公用語を習得しているが、(まったく習得してない社員もいる)
会社が支持すればあらたな言語を学ばせる事も出来る。
ただし、1人に1つの言語を習得させるのにコストが1かかる。
任意の二人の社員が会話する時に、同じ言語を習得していればもちろん大丈夫だが、
そうでなくても他の社員の中に通訳できる者がいるようにしたい。
例)
社員1 言語1
社員2 言語2
社員3 言語1, 3
社員4 言語2, 3
社員5 言語4
社員3と4は言語3を、社員2と4は言語2を使って会話ができる。
社員1と2は社員3と4をダブルで通訳に使えば会話が出来る。
社員5は誰とも会話できない。言語1をなどを学ばせればおk
そのようにする時、最低限のコストを返せ。
制約
2 <= 社員の数・言語の種類 <= 100
方針
社員を一人選び、その深さ優先探索でその社員と会話できる社員にチェックをつける。
これを全員チェックがつくまで繰り返し、探索を開始した数だけ島ができてるから、
これを結ぶために島の数-1が答え。
と思ったら、全員言語を1つも習得していなかった場合のみ、
人数分のコストがかかる。
ソースコード
const int MAX_N = 100; int N, M; /* 社員iは言語jを使えるか? */ bool g[MAX_N+1][MAX_N+1]; /* 社員iをチェックしたか? */ bool chk[MAX_N+1]; void dfs( int i ){ chk[i] = true; for( int j = 1; j <= M; j++ ){ if( !g[i][j] ) continue; for( int k = 1; k <= N; k++ ){ if( chk[k] || !g[k][j] ) continue; dfs(k); } } } int main() { istream& in = cin; in >> N >> M; memset( g, false, sizeof(g) ); bool ok = false; for( int i = 1; i <= N; i++ ){ int n; in >> n; for( int j = 0; j < n; j++ ){ int l; in >> l; g[i][l] = true; ok = true; } } memset( chk, false, sizeof(chk) ); int cost = 0; for( int i = 1; i <= N; i++ ){ if( chk[i] ) continue; cost++; dfs(i); } // 言語を習得している者が誰もいない場合は1引かない cost -= ok ? 1 : 0; cout << cost << endl; return 0; }