问题描述
你在某社交网站上面注册了一个新账号，这个账号有(n(nleq 10^5))次记录。要么就是你更改过一次ID，要么就是一个ID为(s(|s|leq 40))的朋友访问过你的空间。
你有(m(mleq 40))个朋友。每一个朋友都会访问你的空间至少一次。如果这一个朋友每一次访问你的空间的时候，你的ID和它的ID一样，那么他就会高兴。 求你最多能让多少人高兴。
输入格式
第一行一个两个正整数n,m. 接下来n行每行表示一次记录，有如下两种格式：
1
2 s
其中1表示你更改过一次ID，2表示你的一个ID为s的朋友访问过一次你的空间。
保证第一个记录一定是1。
输出格式
一行，一个正整数，表示最多能让多少个朋友高兴。
样例输入
5 3
1
2 motarack
2 mike
1
2 light
样例输出
2
解析
如果把每个人出现的时间段记录下来，就得到了每一个人的出现的时间段的集合。而如果两个人的集合的交集是空集，那么这两个人就可以同时高兴。这样，问题就转化为了求最多的人使这些人出现时间的集合交集为空。把交集不为空的两个人连边，这就变成了一个图上最大独立集的问题。
具体关于交集的判断，可以用bitset对每个人维护一个二进制数，如果两个人的二进制数的与不为0，就说明有交集。
代码
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <bitset>
#include <algorithm>
#define N 100002
#define M 42
using namespace std;
int head[M],ver[M*M],nxt[M*M],l;
int n,m,i,j,cnt1,cnt2,ans,p[M];
bool vis[M];
map<string,int> d;
bitset<N> b[M];
void insert(int x,int y)
{
l++;
ver[l]=y;
nxt[l]=head[x];
head[x]=l;
}
int main()
{
cin>>n>>m;
for(i=1;i<=m;i++) p[i]=i;
for(i=1;i<=n;i++){
int op;
string s;
cin>>op;
if(op==1) cnt1++;
else{
cin>>s;
if(d[s]==0) d[s]=++cnt2;
b[d[s]][cnt1]=1;
}
}
for(i=1;i<=m;i++){
for(j=i+1;j<=m;j++){
if((b[i]&b[j]).any()) insert(i,j),insert(j,i);
}
}
int t=100;
while(t--){
random_shuffle(p+1,p+m+1);
int tmp=0;
memset(vis,0,sizeof(vis));
for(i=1;i<=m;i++){
if(!vis[p[i]]){
tmp++;
for(j=head[p[i]];j;j=nxt[j]) vis[ver[j]]=1;
}
}
ans=max(ans,tmp);
}
printf("%d
",ans);
return 0;
}