问题描述

你在某社交网站上面注册了一个新账号，这个账号有\(n(n\leq 10^5)\)次记录。要么就是你更改过一次ID，要么就是一个ID为\(s(|s|\leq 40)\)的朋友访问过你的空间。

你有\(m(m\leq 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\n",ans);

	return 0;

}