传送门
发现自己不会求最大团了可海星
如果将每一个朋友看做点,将两个\(1\)之间存在\(2\)操作的所有朋友之间互相连边,那么我们最后要求的就是这个图的最大独立集。
某个图的最大独立集就是反图的最大团
然后暴力dfs求最大团即可
#include
#include
#include
//This code is written by Itst
using namespace std;inline int read(){int a = 0;char c = getchar();bool f = 0;while(!isdigit(c) && c != EOF){if(c == '-')f = 1;c = getchar();}if(c == EOF)exit(0);while(isdigit(c)){a = a * 10 + c - 48;c = getchar();}return f ? -a : a;
}bitset < 41 > Edge[41] , cur , choose;
string mod[41] , s;
int N , M , cnt , maxN;inline int find(){for(int i = 1 ; i <= cnt ; ++i)if(mod[i] == s)return i;mod[++cnt] = s;return cnt;
}void dfs(int x){if(choose.count() + x <= maxN)return;if(!x){maxN = choose.count();return;}if((Edge[x] & choose) == choose){choose.set(x);dfs(x - 1);choose.reset(x);}dfs(x - 1);
}int main(){
#ifndef ONLINE_JUDGEfreopen("in","r",stdin);//freopen("out","w",stdout);
#endifN = read();M = read();for(int i = 1 ; i <= M ; ++i)Edge[i].set();for(int i = 1 ; i <= N ; ++i)if(read() == 1)cur.reset();else{cin >> s;int t = find();if(!cur[t]){for(int i = 1 ; i <= cnt ; ++i)if(cur[i])Edge[i][t] = Edge[t][i] = 0;cur.set(t);}}dfs(M);cout << maxN;return 0;
}