假设一头牛会所有语言……
那你不就被hack了吗
by guodong @ 2019-05-01 12:58:48
你应该连牛而不是连语言呀
by guodong @ 2019-05-01 12:59:05
@[月见之免](/space/show?uid=81372) %%%nb
by _H1kar1 @ 2019-05-01 14:06:46
@[月见之免](/space/show?uid=81372) 想了想没想通怎么连牛-_-|||
by _H1kar1 @ 2019-05-01 14:07:48
@[月见之免](/space/show?uid=81372) 这个思路连的也是牛啊,对于向量lan[i]来说里面的元素是掌握它的牛的编号..
by _H1kar1 @ 2019-05-01 14:12:08
跪了,今天又查一早上毫无进展
by _H1kar1 @ 2019-05-02 13:01:16
跪了,今天放学回家路上想出来了
by _H1kar1 @ 2019-05-02 18:03:52
#### 之前的代码没有考虑到可能存在某一语言没有牛会的情况,改一下并查集的初始化就能A了
```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN=10000,MAXM=30000;
int f[MAXM+3];
int find(int p){
if(f[p]!=p) f[p]=find(f[p]);
return f[p];
}
void unite(int a,int b){
if(find(a)!=find(b)){
f[f[a]]=f[b];
}
}
vector<int> lan[MAXM+3];
int main(){
int n,m,ans;
cin>>n>>m;//n cows,m languges
memset(f,0,sizeof(f));
int nn,l;
for(int i=1;i<=n;i++){//list all cows
cin>>nn;
for(int j=1;j<=nn;j++){
cin>>l;
lan[l].push_back(i);
f[i]=i;
}
}
for(int i=1;i<=m;i++){
for(int j=0;j<lan[i].size();j++)
unite(lan[i][0],lan[i][j]);
}
for(int i=1;i<=n;i++)
if(f[i]==i)ans++;
cout<<ans-1<<endl;
return 0;
}
```
by _H1kar1 @ 2019-05-02 18:05:21