Code Names(最大独立集合)

题意: 你得到了单词集W，一组N个单词，它们是彼此的相同字母异序词，任何单词中都没有重复的字母。 一组单词S⊆W称为“无交换”，指如果无法通过交换x中的一对字母（不一定相邻）将单词x∈S转换为另一个单词y∈S。 你需要从给定的单词集W中找出最大的无交换集S的大小。

前置知识 最小点覆盖：连接所有边所需的最小顶点数 最大匹配数：图中形成一对一对的点的对数。 最大独立集 = = = 总点数 − - − 最小点覆盖 二分图： 图中至少存在两个点，且图中所有回路的长度均为偶数。 在二分图中： 最小顶点覆盖 = 最大匹配数

证明：首先，最小顶点覆盖一定>=最大匹配，因为假设最大匹配为n，那么我们就得到了n条互不相邻的边，光覆盖这些边就要用到n个点。这里事实上就可以看出最小顶点覆盖和最大匹配的不同了，最大匹配的点一定是两两成对的，而最小顶点覆盖还有相对孤立的点。注意是相对孤立，并不是他们之间肯定没有边，而是不属于匹配范围内的。那么匹配范围外的节点，一种就是有边和匹配范围内元素相连但是没有匹配到，一种就是没边。 有边的话这个边就连在了匹配范围内，那这个顶点覆盖代表元素就是既可以连接上匹配元素，又可以连接到非匹配元素，相当于这个非匹配范围内的元素被这个“特殊顶点”覆盖，最小顶点覆盖数并没有增加； 那么完全没边的孤立节点呢？好嘞，最小点集覆盖目的就是要覆盖所有的边，既然这个节点没有边相连，那还要你干毛？滚吧。这样依然没有影响最小顶点覆盖数。 至此，匹配范围外的所有节点都不可能影响到最小顶点覆盖数，所以两者完全相等 思路 很容易想到是最大独立子集， 就是求一个集合， 此集合中的点两两之间没有边相连。 由最大独立集 = 总点数 - 最小点覆盖； 现在来看一下建图， 显然很容易可以通过暴力建图，枚举任意两个字符串看是不是能过通过交换得到。通过建图可以得到的就是这个图建起来不可能有奇环， 应为如果 A -> B -> C -> A 那么必然 C == B（但每个字符串都不同） 所以这是一个二分图， 所以此题最大独立集 = 总点数 - 最大匹配数

其余细节见于代码

#include <bits/stdc++.h>

using namespace std;

const int N = 502;
int a[N][N];
int vis[N], vis1[N];
int n;
string s[N];

bool dfs(int x)
{
          
   
	if(vis[x] == 1) return false;
    vis[x] = 1;
    for(int i = 1; i <= n; i++)
    {
          
   
        if(a[x][i])
        {
          
   
            if(vis1[i] == 0 || dfs(vis1[i]))
            {
          
   
                vis1[i] =  x;
                vis1[x] = i;
                return true;
            }
        }
    }
    return false;
}
int main()
{
          
   
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
          
   
        cin >> s[i];
    }
    for(int i = 1; i <= n; i++)
    {
          
   
        for(int j = 1; j <= n; j++)
        {
          
   
            int p = 0;
            for(int k = 0; k < s[i].size(); k ++)
            {
          
   
                if(s[i][k] != s[j][k])
                    p ++;
            }
            if(p == 2) a[i][j] = 1;
        }
    }
    int ans = n;
    for(int i = 1; i <= n; i++)
    {
          
   
         memset(vis, 0, sizeof vis);
        if(vis1[i] == 0 && dfs(i))
        {
          
   
            ans -= 1;
        }
    }
    cout << ans << endl;
    return 0;
}