ZOJ:3641 Information Sharing
1931 ワード
标题:言わない.
構想:明らかな並列調査集.データ量は比較的小さく、セットはsetでメンテナンスできます.唯一注意すべき点は、メモリが爆発する可能性があるため、統合するたびに元のsetが空になることです.
構想:明らかな並列調査集.データ量は比較的小さく、セットはsetでメンテナンスできます.唯一注意すべき点は、メモリが爆発する可能性があるため、統合するたびに元のsetが空になることです.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long LL;
int cnt;
map<string,int> mp;
const int maxn=100005;
int father[maxn];
set<int> s[maxn];
void init(int i)
{
father[i]=i;
}
int find(int p)
{
return p==father[p]?p:father[p]=find(father[p]);
}
void unio(int a,int b)
{
int fa=find(a),fb=find(b);
if(fa!=fb)
{
father[fa]=fb;
for(set<int>::iterator it=s[fa].begin(); it!=s[fa].end(); ++it)
{
s[fb].insert(*it);
}
s[fa].clear();
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
char a[20],b[20];
mp.clear();
cnt=0;
while(n--)
{
scanf("%s",a);
if(a[0]=='a')
{
scanf("%s",b);
mp[string(b)]=++cnt;
init(cnt);
s[cnt].clear();
int m;
scanf("%d",&m);
for(int i=0; i<m; ++i)
{
int x;
scanf("%d",&x);
s[cnt].insert(x);
}
}
else if(a[0]=='s')
{
char c[20];
scanf("%s%s",b,c);
int x=mp[string(b)],y=mp[string(c)];
unio(x,y);
}
else
{
scanf("%s",b);
int f=find(mp[string(b)]);
printf("%d
",s[f].size());
}
}
}
return 0;
}