{"id":648,"date":"2009-11-01T15:25:00","date_gmt":"2009-11-01T07:25:00","guid":{"rendered":"http:\/\/localhost\/?p=5"},"modified":"2009-11-01T15:25:00","modified_gmt":"2009-11-01T07:25:00","slug":"sgu_318","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=648","title":{"rendered":"sgu 318"},"content":{"rendered":"

http:\/\/acm.sgu.ru\/problem.php?contest=0&problem=318
\u770b\u4e0a\u53bb\u6709\u70b9\u5c0f\u96be\u5ea6\u3002\u3002\u5b9e\u9645\u4e0a\u5f88\u6c34\u3002\u3002
\u4e00\u5f00\u59cb\u8fd8\u60f3DP\u4ec0\u4e48\u3002\u3002\u771f\u662f\u6c99\u8336\u3002\u3002\u3002
\u6709\u4e24\u79cd\u65b9\u6cd5\u3002\u3002\u4e00\u79cd\u4eceuser\u7684\u89d2\u5ea6\u8003\u8651\u3002\u3002\u6bcf\u4e2auser\u90fd\u6709\u9700\u8981\u7684\u5feb\u3002\u3002\u53ea\u8981\u7528\u7c7b\u4f3c\u77e9\u5f62\u5207\u5272\u7684\u529e\u6cd5\u3002\u3002\u4e0d\u65ad\u53d6\u4ea4\u96c6\u5c31OK\u4e86\u3002\u3002
\u8fd8\u6709\u4e00\u79cd\u4eceresource\u89d2\u5ea6\u8003\u8651\u3002\u3002\u4e24\u4e2aresource\u53ef\u4ee5\u5408\u5e76\u6210\u4e00\u7ec4\u5f53\u4e14\u4ec5\u5f53\u9700\u8981\u4ed6\u4eec\u7684\u4eba\u662f\u4e00\u6837\u7684\u3002\u3002\u7528\u5e76\u5dee\u96c6\u5b9e\u73b0\u5c31OK\u4e86\u3002\u3002\u5f53\u7136\u8981\u5c3d\u53ef\u80fd\u591a\u7684\u5408\u5e76\u3002\u3002
PS\u4e3a\u4e86\u5b9e\u73b0\u65b9\u4fbf\u3002\u3002\u53ef\u4ee5\u5229\u7528\u96c6\u5408pascal\u91cc\u9762\u662fset\u3002\u3002C++\u91cc\u9762\u662fbitset\u3002\u3002\u5f88\u65b9\u4fbf\u7684\u3002\u3002
Code\u3002\u3002\u3002
#include<bitset>
#include<iostream>
using namespace std;
const int maxn=100+10;
int n,m,ans=0;
bitset<100> Q[maxn];
int F[maxn];
int find(int x)
{
if(F[x]!=x) F[x]=find(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=find(x);y=find(y);
if(x!=y)
ans–;
F[x]=y;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) F[i]=i;
for(int i=0;i<m;i++)
{
int t,s;cin>>t;
while(t–)
{
cin>>s;s–;
Q[s][i]=true;
}
}
for(int i=0;i<n;i++) if(Q[i].count())
{
ans++;
for(int j=i+1;j<n;j++)
if(Q[i]==Q[j])
Union(i,j);
}
cout<<ans<<endl;
}       <\/p>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

http:\/\/acm.sgu.ru\/problem.php?contest=0&problem=318\u770b\u4e0a\u53bb\u6709\u70b9\u5c0f\u96be\u5ea6\u3002\u3002\u5b9e\u9645\u4e0a\u5f88\u6c34\u3002\u3002\u4e00\u5f00\u59cb\u8fd8\u60f3DP\u4ec0\u4e48\u3002\u3002\u771f\u662f\u6c99\u8336\u3002\u3002\u3002\u6709\u4e24\u79cd\u65b9\u6cd5\u3002\u3002\u4e00\u79cd\u4eceuser\u7684\u89d2\u5ea6\u8003\u8651\u3002\u3002\u6bcf\u4e2auser\u90fd\u6709\u9700\u8981\u7684\u5feb\u3002\u3002\u53ea\u8981\u7528\u7c7b\u4f3c\u77e9\u5f62\u5207\u5272\u7684\u529e\u6cd5\u3002\u3002\u4e0d\u65ad\u53d6\u4ea4\u96c6\u5c31OK\u4e86\u3002\u3002\u8fd8\u6709\u4e00\u79cd\u4eceresource\u89d2\u5ea6\u8003\u8651\u3002\u3002\u4e24\u4e2aresource\u53ef\u4ee5\u5408\u5e76\u6210\u4e00\u7ec4\u5f53\u4e14\u4ec5\u5f53\u9700\u8981\u4ed6\u4eec\u7684\u4eba\u662f\u4e00\u6837\u7684\u3002\u3002\u7528\u5e76\u5dee\u96c6\u5b9e\u73b0\u5c31OK\u4e86\u3002\u3002\u5f53\u7136\u8981\u5c3d\u53ef\u80fd\u591a\u7684\u5408\u5e76\u3002\u3002PS\u4e3a\u4e86\u5b9e\u73b0\u65b9\u4fbf\u3002\u3002\u53ef\u4ee5\u5229\u7528\u96c6\u5408pascal\u91cc\u9762\u662fset\u3002\u3002C++\u91cc\u9762\u662fbitset\u3002\u3002\u5f88\u65b9\u4fbf\u7684\u3002\u3002Code\u3002\u3002\u3002#include<bitset>#include<iostream>using namespace std;const int maxn=100+10;int n,m,ans=0;bitset<100> Q[maxn];int F[maxn];int find(int x){if(F[x]!=x) F[x]=find(F[x]);return F[x];}void Union(int x,int y){x=find(x);y=find(y);if(x!=y)ans–;F[x]=y;}int main(){cin>>n>>m;for(int i=0;i<n;i++) F[i]=i;for(int i=0;i<m;i++){int t,s;cin>>t;while(t–){cin>>s;s–;Q[s][i]=true;}}for(int i=0;i<n;i++) if(Q[i].count()){ans++;for(int j=i+1;j<n;j++)if(Q[i]==Q[j])Union(i,j);}cout<<ans<<endl;}      <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/648"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=648"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/648\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=648"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=648"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=648"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}