Kattis - codenames
题目：
You are given W, a set of N words that are anagrams of each other. There are no duplicate letters in any word. A set of words S? W is called “swap-free” if there is no way to turn a word x∈ S into another word y∈ S by swapping only a single pair of (not necessarily adjacent) letters in x. Find the size of the largest swap-free set S chosen from the given set W.
Input
The first line of input contains an integer N
(1≤ N≤500). Following that are N lines each with a single word. Every word contains only lowercase English letters and no duplicate letters. All N words are unique, have at least one letter, and every word is an anagram of every other word.
Output
Output the size of the largest swap-free set.
Sample Input 1
6
abc
acb
cab
cba
bac
bca
Sample Output 1
3
Sample Input 2
11
alerts
alters
artels
estral
laster
ratels
salter
slater
staler
stelar
talers
Sample Output 2
8
Sample Input 3
6
ates
east
eats
etas
sate
teas
Sample Output 3
4
匈牙利算法求最大匹配从而得出最大独立集
代码
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
const int N = 1111;
using namespace std;int n;
vector<int>mp[N];
char s[N][N];
int a[N];
int vis[N];int Find(int x)
{
for(int i=0; i<(int)mp[x].size(); i++){
if(!vis[mp[x][i]]){
vis[mp[x][i]]=1;if(!a[mp[x][i]]||Find(a[mp[x][i]])){
a[mp[x][i]]=x;return 1;}}}return 0;
}void solve(){
cin>>n;for(int i=1; i<=n; i++){
cin>>s[i];}int l=strlen(s[1]);for(int i=1; i<=n; i++){
for(int j=i+1; j<=n; j++){
int num=0;for(int k=0; k<l; k++){
if(s[i][k]!=s[j][k])num++;if(num>2)break;}if(num==2){
mp[i].push_back(j);mp[j].push_back(i);}}}int cnt=0;for(int i=1; i<=n; i++){
memset(vis,0,sizeof(vis));if(Find(i))cnt++;}cout<<n-cnt/2<<endl;
}int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}