Codeforces #170 Div1. A. Learning Languages

さてここからが本番。とはいえまだAなのでさほど難しくない。
http://codeforces.com/contest/277/problem/A

問題

N人の従業員がさまざまな言語をしゃべる。
直接同じ言語をしゃべらない従業員同士も、両方の言葉をしゃべれる従業員がいれば意志疎通が図れる。
全従業員が意志疎通を図るために、追加で何人が何個の言語を勉強すればよいか最小値を答える。

解法

従業員および言語を点とする無向グラフを作り、連結成分の数を数える。
(連結成分の数)-1が答え。
ただし例外として、全員が１つも言語をしゃべれない場合は、人数分(＝連結成分の数)が答えとなる。

int N,M;
vector<int> E[101],G[101];
int vis[101],visg[101];

void dfs(int cur) {
	int i,j,k,l;
	vis[cur]=1;
	
	FOR(i,E[cur].size()) {
		j=E[cur][i];
		if(visg[j]) continue;
		visg[j]++;
		FOR(k,G[j].size()) {
			l = G[j][k];
			if(vis[l]==0) dfs(l);
		}
	}
}

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	N=GETi();
	M=GETi();
	
	nt=0;
	FOR(i,N) {
		x=GETi();
		if(x>0) nt++;
		FOR(j,x) {
			y=GETi()-1;
			E[i].push_back(y);
			G[y].push_back(i);
		}
	}
	
	if(nt==0) {
		_P("%d\n", N);
		return;
	}
	
	ZERO(vis);
	num=0;
	FOR(i,N) {
		if(vis[i]==1) continue;
		num++;
		dfs(i);
	}
	
	_P("%d\n",num-1);
	return;
}

まとめ

解法自体は難しくないけど、A問題にしてはコード量が多いな。