Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/contest/277/problem/A
题意：有n个人，每个人会一定数目的语言（可能为0），一个人学一门语言的代价为1，人和人之间沟通可以通过任意个中间人翻译。问最少的代价使得这n个人可以相互沟通。
思路：建图方式如下：第i个人会语言j，那么连上i和j+n。然后跑一遍dfs,使得1..n这n个点都被访问过。
结果wa4…觉得算法没问题。。看了官方题解。。发现果然有情况没有考虑到。如果所有的人都什么语言都不会的话，那么答案是不能-1的。。因为。。语言和语言之间不能连边。。改了之后A了。。有点开心。。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月05日 星期六 20时55分14秒
4File Name :code/cf/problem/277A.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25
26
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E2+5;
34int n,m;
35vector<int>edge[N];
36bool vis[N];
37
38void dfs( int x)
39{
40 // cout<<"x:"<<x<<endl;
41 vis[x] = true;
42 for ( int i = 0 ; i < edge[x].size(); i ++)
43 {
44 int v = edge[x][i];
45// cout<<"v:"<<v<<endl;
46 if (!vis[v])
47 {
48 dfs(v);
49 }
50 }
51}
52int main()
53{
54 #ifndef ONLINE_JUDGE
55 freopen("code/in.txt","r",stdin);
56 #endif
57
58 scanf("%d %d",&n,&m);
59 int p = 0;
60 for ( int i = 1 ; i <= n ; i++)
61 {
62 int k ;
63 scanf("%d",&k);
64 if (k!=0) p = -1;
65 for ( int j = 0 ; j < k ; j++)
66 {
67 int x;
68 scanf("%d",&x);
69 edge[i].push_back(x+n);
70 edge[x+n].push_back(i);
71 }
72 }
73 int cnt = 0 ;
74 ms(vis,false);
75 for ( int i = 1 ; i <= n ; i++)
76 {
77 if (!vis[i])
78 {
79 dfs(i);
80 cnt++;
81 }
82 }
83 cout<<cnt+p<<endl;
84
85 #ifndef ONLINE_JUDGE
86 fclose(stdin);
87 #endif
88 return 0;
89}