USACO OPEN11 Learning Languages

Farmer John's N (2 <= N <= 10,000) cows, conveniently numbered 1..N,
are fluent in some M (1 <= M <= 30,000) languages, also conveniently
numbered from 1..M. Cow i can speak in K_i (1 <= K_i <= M) languages,
namely L_i1, L_i2,..., L_{iK_i} (1 <= L_ij <= M). FJ's cows aren't
THAT smart, so the sum of K_i over all cows i is at most 100,000.

Two cows can't directly talk to each other unless both speak a
common language. However, cows can pass messages along, translating
if necessary. In other words, cows A and B can have a conversation
if and only if there exists a sequence of cows T_1, T_2, ..., T_k
such that A and T_1 share a language, T_1 and T_2 share a language,
etc., and T_k and B share a language.

Farmer John wishes that his cows could be even more social, so he
wants all his cows to be able to socialize with any other cow. He
can buy books to teach any one of his cows any language he pleases.
Being a fairly frugal farmer, FJ wants to purchase the minimum
number of books necessary to enable all of his cows to speak to
each other. Help him determine:

    * The minimum number of books he must purchase

    * Any set of books assigned to cows in any order which will
      help him meet this goal; a program will grade your output.

By way of example, suppose there are three cows named Alberta,
Bessie, and Contessa along with three languages denoted as #1, #2,
and #3. Alberta can speak languages #2 and #3, Bessie can speak
language #2, and Contessa can speak language #1. Currently, Alberta
and Bessie can talk to each other, but Contessa is left alone.

                   #1   #2   #3
       Alberta           x    x
       Bessie            x
       Contessa     x

FJ wants to fix this situation, so he can buy Contessa a book to
teach her language #2. This will ensure all cows speak the same
language, so they can all communicate with one another.

Note that an alternate solution exists: instead, FJ could buy
Contessa a book to teach her language #3. Not all cows would speak
the same language, but this would still be a valid solution because
Contessa could communicate through Alberta (who also speaks language
#3) if she wants to talk to Bessie. Other alternatives exist, and any
valid alternate solution will also be accepted.

PROBLEM NAME: llang

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes the languages that cow i can speak
        with (K_i)+1 space-separated integers: K_i, L_i1,
        L_i2,...,L_i{K_i}.

SAMPLE INPUT (file llang.in):

3 3
2 3 2
1 2
1 1

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of books that FJ
        must purchase.

* Lines 2..B+1: Line i+1 contains two space-separated integers: the
        language id # and the id # of the cow to receive book i. If
        multiple solutions exist, print any one.

SAMPLE OUTPUT (file llang.out):

1
2 3

**********************************************************************

本人使用并查集解决这个问题。

先用M个链表保存会某个语言的牛的编号。然后把会相同语言的牛全部merge掉。最后

统计联通分量的个数ccnt。所需要的最少的书本数就是ccnt-1.

对于安排书本，本人是这样解决的。由上一步可知，不同联通分量之间一定不不存在

相同的语言。因此，任意选取一个被某个联通分量中的牛掌握的语言，然后把ccnt-1

本书分别安排到其他每个联通分量中。 

处理无向图联通性的问题经常使用到并查集。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAXN 100005
05
06 typedef struct node
07 {
08    struct node *next;
09    long v;
10 }node;
11
12 long N,M;
13 long fa[MAXN];   //并查集
14 node *head[30002] = {};   //链表
15 _Bool vis[MAXN] = {};    //辅助数组，判断某个联通分量是否被访问过
16
17 void add(long lang,long v)
18 {
19    node *p = malloc(sizeof(node));
20    p->v = v;
21    p->next = head[lang];
22    head[lang] = p;
23 }
24
25 long getfa(long x)
26 {
27    if(fa[x] != x)
28        fa[x] = getfa(fa[x]);
29    return fa[x];
30 }
31
32 void init()
33 {
34    scanf("%ld%ld\n",&N,&M);
35    long i,k,lang;
36    for(i = 1;i <= N;i ++)
37    {
38        scanf("%ld",&k);
39        while(k --)
40        {
41            scanf("%ld",&lang);
42            add(lang,i);
43        }
44    }
45 }
46
47 void solve()
48 {
49    long i,x,first;
50    long ccnt = 0;
51    node *p;
52    for(i = 1;i <= N;i ++)
53        fa[i] = i;
54    for(i = 1;i <= M;i ++)
55    {
56        if(head[i] != NULL)
57            x = getfa(head[i]->v);
58        for(p = head[i];p != NULL;p = p->next)
59            fa[getfa(p->v)] = x;
60    }
61    for(i = 1;i <= N;i ++)
62    {
63        x = getfa(i);
64        if(!vis[x])
65        {
66            vis[x] = 1;
67            ccnt ++;
68        }
69    }
70    printf("%ld\n",ccnt - 1);
71    for(x = 1;x <= M && head[x] == NULL;x ++);  //find the first lang known by at least one cow
72    first = getfa(head[x]->v);
73    memset(vis,0,sizeof(vis));
74    vis[first] = 1;
75    for(i = 1;i <= N;i ++)
76        if(!vis[getfa(i)])
77        {
78            vis[getfa(i)] = 1;
79            printf("%ld %ld\n",x,i);
80        }
81 }
82
83 int main()
84 {
85    freopen("llang.in","r",stdin);
86    freopen("llang.out","w",stdout);
87    init();
88    solve();
89    fclose(stdout);
90    return 0;
91 }