Difference of Clustering HDU - 5486
题意：有n个实体，新旧两种聚类算法，每种算法有很多聚类，在同一算法里，一个实体只属于一个聚类，然后有以下三种模式。
第一种分散,新算法的某几个聚类是旧算法某个聚类的真子集。
第二种聚合,旧算法的某几个聚类是新算法某个聚类的真子集。
第三种1:1,新算法的某个聚类跟旧算法某个聚类相同。
问每种模式存在多少个?
实路上很明了，就是模拟，而且每个实体最多遍历到一次，所以时间上不用担心。
先把聚类的编号hash，把每个实体分配到相应的聚类里，然后遍历新算法的所有聚类，再遍历每个聚类里的每个实体，用set保存这个实体相应的旧算法的聚类。
然后就是分情况讨论，如果set里的元素大于1，很明显就是分散，我们遍历set里的旧算法的聚类，然后遍历实体，看实体的编号是不是都对应当前遍历的新算法的编号
如果set里元素刚好是1，就看这个唯一对应的旧算法的聚类大小，如果等于当前遍历的新算法的大小，就是1:1了，否则我们考虑聚合的情况，处理跟分散差不多
遍历这个旧算法的聚类里的实体，用set保存这个实体相应的新算法的聚类，遍历set里的新算法的聚类，然后遍历实体，看实体的编号是不是都对应这个旧算法的编号
这里要注意的就是标记一下遍历的新算法的聚类的编号，然后后面遍历到这个聚类直接跳过就行。
具体实现上，stl用的好的话很好实现的，需要注意的就是内存的问题。clear是不会清空内存的，所有会超内存，所以用swap，
还有二维vector，vector<int> pp1[N],pp2[N]这样开的话也会超内存，改成vector< vector<int> > 动态分配内存就OK了。
主要是想保存一些这个swap和二维vector降低内存的方法，还有无序map。解法的话网上有个思路，把给出的关系转换成图，然后dfs判断点的度数就行了。
#include<cstdio>
#include<tr1/unordered_map>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int N=1e6+;
const ll M=1e10+;
tr1::unordered_map<ll,int> mmp;
vector< vector<int> > pp1,pp2;//记录相应的聚类里的实体
set<int> temp;
bool vis[N];
int match1[N],match2[N];//记录实体对应的聚类
int main(){
int t=,T,n,cnt1,cnt2,id1,id2;
ll c1,c2;
scanf("%d",&T);
while(t<=T){
cnt1=cnt2=;
tr1::unordered_map<ll,int>().swap(mmp);
vector< vector<int> >().swap(pp1);
vector< vector<int> >().swap(pp2);
pp1.push_back(vector<int>());
pp2.push_back(vector<int>());
scanf("%d",&n);
for(int i=;i<=n;i++) vis[i]=false;
for(int i=;i<=n;i++){
scanf("%lld%lld",&c1,&c2);
c2+=M;
if(!mmp[c1]) mmp[c1]=++cnt1;
if(!mmp[c2]) mmp[c2]=++cnt2;
id1=mmp[c1];id2=mmp[c2];
if(cnt1>=(int)pp1.size())
pp1.push_back(vector<int>());
if(cnt2>=(int)pp2.size())
pp2.push_back(vector<int>());
pp1[id1].push_back(i);
pp2[id2].push_back(i);
match1[i]=id1;
match2[i]=id2;
}
int ans1=,ans2=,ans3=;
for(int i=;i<=cnt1;i++){
if(vis[i]) continue;
set<int>().swap(temp);
for(int j=;j<(int)pp1[i].size();j++)
temp.insert(match2[pp1[i][j]]);
if((int)temp.size()>){
bool flag=true;
for(set<int>::iterator it=temp.begin();it!=temp.end()&&flag;it++){
id2=*it;
for(int k=;k<(int)pp2[id2].size()&&flag;k++){
id1=pp2[id2][k];
if(match1[id1]!=i) flag=false;
}
}
if(flag) ans1++;
}else{
id2=*temp.begin();
if((int)pp2[id2].size()!=(int)pp1[i].size()){
set<int>().swap(temp);
for(int j=;j<(int)pp2[id2].size();j++){
id1=pp2[id2][j];
if(match1[id1]!=i) temp.insert(match1[id1]);
}
bool flag=true;
for(set<int>::iterator it=temp.begin();it!=temp.end();it++){
id1=*it;
vis[id1]=true;
for(int k=;k<(int)pp1[id1].size();k++){
int id3=pp1[id1][k];
if(match2[id3]!=id2){
flag=false;
break;
}
}
}
if(flag) ans2++;
}else ans3++;
}
}
printf("Case #%d: %d %d %d\n",t++,ans1,ans2,ans3);
}
return ;
}
stl好啊