bzoj3296[USACO2011 Open] Learning Languages*

bzoj3296[USACO2011 Open] Learning Languages

题意：

n头奶牛，每头牛会一些语言，总共有m种语言。求需让某些奶牛学会的最小语言数使得任意两只奶牛直接或间接可以用同种语言聊天（比如a会语言1，b会语言1和2，c会语言2和3，d会语言3则他们两两可以交流）。n≤10000，m≤30000。

题解：

如果一头奶牛会某种语言，则将这头奶牛与这种语言连边，最后答案为所得图联通块数-1。求联通块我用的是并查集。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 40010
 7 using namespace std;
 8 
 9 inline int read(){
10     char ch=getchar(); int f=1,x=0;
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
13     return f*x;
14 }
15 int fa[maxn],n,m,ans; bool calced[maxn];
16 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
17 void merge(int x,int y){int xx=find(x),yy=find(y); if(xx!=yy)fa[xx]=yy;}
18 int main(){
19     n=read(); m=read(); inc(i,1,n+m)fa[i]=i;
20     inc(i,1,n){
21         int x=read(); inc(j,1,x){int y=read(); merge(i,n+y);}
22     }
23     inc(i,1,n){int x=find(i); if(!calced[x])ans++,calced[x]=1;}
24     printf("%d",ans-1); return 0;
25 }

20161110