最大独立集的概念
独立集
来自oi-wiki
在上面的描述中，V是代表的点集，而E代表的是边集
独立集以及最大独立集均是点的 集合
从字面意思来说，一张图的最大独立集就是独立集中尺寸最大的
如果说两个点之间是独立的那么说这两个点之间就没有边相连
匹配
上面所提到的独立集是点的集合，而匹配则是边的集合
在这个集合中，任一两条边之间是不含有公共的端点的
从字面意思来说，最大匹配也就是所包含的最大数量的边的数量，且任意两个边和边之间没有公共点
对于下面的图来说：
对于这种图，有4个点3条边
最大独立集就是{2,3,4}
最大匹配就是{1-2} {1-3} {1-4} 中的任意一个其中1-2表示的意思为点1和点2之间的边
概念之间的关系及性质
- 最大独立集 = n - 最大匹配
- 最大匹配 = 最小点覆盖
- 最大独立集 = n - 最小点覆盖
- 最大团 = 补图的最大独立集
- 最大独立集 = 补图的最大团
补图：如果n个点两两之间没有边，那么将这两个点连在一起，如果之前两点之间有边，那么就将这两个点之间的边去掉-》得到补图
整理到这里，我们可以发现在上面的图中，要是想知道二分图的最大独立集
可以先做出图的补图，得到补图之后可以从任意两点之间不相邻转换为两点之间相邻
所以说很容易就能够看出这个图的最大独立集大小就是3 -> {2,3,4}
二分图的最大独立集 -> 一个最大的点的集合，该集合内的任意两点没有边相连。
二分图最大团的定义 -> 一个最大的点的集合，该集合内的任意两点都有边相连。
所以说上面的4.5.是相反的关系
例题
2021年度训练联盟热身训练赛第一场 B Code Names
题目描述
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 S⊆WS⊆W is called “swap-free” if there is no way to turn a word x ∈ S x∈Sx∈S into another word y ∈ S y∈Sy∈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.
输入描述:
The first line of input contains an integer N (1 ≤ N ≤ 500 1≤N≤5001≤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 the size of the largest swap-free set.
示例1
输入
6 abc acb cab cba bac bca
输出
3
示例2
输入
11 alerts alters artels estral laster ratels salter slater staler stelar talers
输出
8
示例3
输入
6 ates east eats etas sate teas
输出
4
要是求最大匹配 / 最小点覆盖问题，可以选择比较简单的匈牙利算法，代码篇幅比较短还比较容易实现
具体的博客内容推荐 知乎
具体的思路是我们可以将之间能够swap free的建立关系（连一条边无向边）
然后跑匈牙利算法
然后在遍历n个点的时候，将符合条件的点进行统计-> cnt，然后 temp = cnt / 2 -> 会有一半的重复
最后answer = n - temp;
- judge函数用来判断两个字符串之间是不是能够建立联系，如果是能够通过交换两个字母得到，就在两个字符串之间建立一条边（实际在操作的过程中只是需要对字符串的下表进行建边就好，不会对答案产生影响）
- 在判断节点是否可行的时候注意将之前加的标注数组vis进行清空，否则会对答案产生影响
- a数组是用来存储边的，vis数组用来标记节点是否已经被访问过，fa数组用来存储一个节点已经配对的节点的编号
- 对某一个点进行判断的时候，可以将所需要判断的点传参进入dfs函数，然后遍历和这个点相连的所有点节点，当与x节点相连的点没有被访问过的时候，我们就可以将这个点标记为访问过，并递归处理这个点，处理的条件是这个点没有与之建立匹配关系的节点，或者是这个点可以进行匹配，用上面博客里的一句话就是：//如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配。其中，左侧可以理解为二分图的另一部分，当然是和这个点不在同一块的部分
- 然后就可以输出n - cnt / 2即可
int a[507][507]; int fa[507]; int n; string s[507]; bool vis[507]; bool judge(string a,string b){ if(a.size() != b.size()) return false; int len = a.size(); int cnt = 0; int pos1,pos2; for(int i=1;i<=len;i++){ if(a[i-1] != b[i-1]){ cnt ++; if(cnt > 2) return 0; if(cnt == 1) pos1 = i-1; else if(cnt == 2) pos2 = i-1; } } if(a[pos1] != b[pos2]) return false; if(a[pos2] != b[pos1]) return false; return true; } bool dfs(int x){ for(int i=1;i<=n;i++){ if(i == x) continue; if(a[x][i] && !vis[i]){ vis[i] = 1; if(!fa[i] || dfs(fa[i])){ fa[i] = x; return true; } } } return false; } int main() { n = read; memset(fa,0,sizeof fa); memset(a,0,sizeof a); for(int i=1;i<=n;i++) cin >> s[i]; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(judge(s[i],s[j])){ a[i][j] = 1; a[j][i] = 1; } } } int ans = 0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(dfs(i)) ans ++; } cout<<(n - (ans >> 1)) <<endl; return 0; }
